Cracking open secure

messages would be easy if only you knew how

to factor huge numbers. In this episode, we’ll

show you how with a twist. One of the main methods

of cryptography, the encoding and decoding

secure communications, uses really big prime numbers. For a detailed

description, check out some of the great videos we’ve

linked to in the description, but for now, here’s

the distilled version. It’s pretty easy for a computer

to find big prime numbers and multiply them together, but

it’s really hard for a computer to do the opposite– find the prime factors

of a really big number. The prime factors of a number

are all the prime numbers that evenly divide it. Normally, RSA cryptography uses

these prime factors like keys to decrypt messages. So if you want to

eavesdrop, you’ll need to find one of

these keys to hack in– that is, you’ll need to find the

prime factors of a big number, and we’re talking really big,

as in hundreds of digits long. Let’s try a small example. What are the prime

factors of 35? Well, they’re 5 and 7. How did you figure that out? Probably just by

looking at it, but even if you had forgotten

that fact, you could have just checked all the

prime numbers smaller than 35. Does two divide it? No. Does 3? No. Does 5? Yes. And so on. How boring. And more importantly for a

computer, how time consuming. We’ll need to do something

more strategic to factor really big numbers. Enter one of the great

math heroes, Euler. Along with many,

many other things Euler thought a lot

about prime numbers, relatively prime numbers,

and modular arithmetic, which is basically all the math

underlying RSA cryptography. So it makes sense that

we’d use similar math to break the algorithm. Modular arithmetic

is what happens when you count in a circle. Counting modulo 5,

or mod 5 for short, goes 0, 1, 2, 3 4, 0, 1,

2, 3 4, 0, 1, 2, and so on. We just use the numbers

less than 5 on repeat. We tell time mod 12 or mod 24

depending on your convention. This cyclical counting extends

to the arithmetic operations. So 1 plus 2 mod 5 is still just

3, but 2 plus 3 mod 5 is 0, and 2 times 3 is 1 mod 5. Another way to think

about modular asthmatic is in terms of the remainder

when dividing numbers. So here’s a slightly

more formal definition. a is congruent to x mod n means

that when we divide a by n the remainder is x. So 2 times 3 is 6, but

when we divide 6 by 5, the remainder is 1. So 2 times 3 mod 5 is 1. Euler noticed something

about modular arithmetic and exponentiation. Let’s look at the powers of 3– 3, 9, 27, 81, 243, and so on. And let’s look at

them all mod 10. It’s easy to figure out

what things are mod 10 because it’s just the

remainder when you divide by 10, which is the ones digit. So mod 10 our sequence is 3,

9, 7, 1, 3, 9,7, 1, and so on. Let’s repeat the

same experiment, but instead of looking at

the powers of 3 mod 10, let’s look at the

powers of 2 mod 7. The powers of 2 are 2, 4,

8, 16, 32, 64, and so on. And mod 7 we get 2, 4,

1, 2, 4, 1, and so on. What do you observe? The sequence of powers just

gets bigger and bigger, but the modular versions

of the sequence cycle. They repeat the same

pattern over and over again, and the last digit of

that pattern is always 1. As long as x and n

are relatively prime, meaning they share no prime

factors, the sequence x mod N, x squared mod N, x cubed mod

N, x to the fourth mod N, and so on will always

have this property. We call the length of the

repeating pattern the period. So the period of 3 mod 10 is 4,

and the period of 2 mod 7 is 3. Here’s why the

period is important. If the period of x mod

N is some number r, then r is the smallest

number such that x to the r is congruent to 1 mod n. For example, 3 to the fourth

is congruent to 1 mod 10, but 3 for the first, 3 squared,

and 3 cubed are not 1 mod 10, but let’s get back

to our original goal. What does all this stuff

about modular arithmetic, exponentiation, and

periods have to do with factoring large numbers? Let’s say I give you a number n. I tell you n equals p times q

for two prime numbers p and q, but I don’t tell you

anything about those primes. Your job is to find them. Here’s how you’ll do it. Step one– pick any

number smaller than n. Let’s call the number

you selected a. Check to make sure

that a and n are relatively prime by

computing the greatest common divisor of a and n. The greatest common

divisor of two numbers is the biggest integer

that divides them both, so it’s 1 if the two numbers

are relatively prime. The Euclidean algorithm is

a quick and standard way to find the GCD of two numbers. If they have a

divisor in common, that’s a factor of n, which is

what you’ve been looking for, and you’ve saved yourself

the rest of the steps. Step two– compute the period

of a mod N. Let’s call it r. For the sake of

example, let’s say you’re trying to find

the factors of 35. So n equals 35, and

you pick a equals 8 since it’s relatively

prime to 35. Then with a little computation

we can see that r equals 4. To make all the

arithmetic work out, we’re going to need

to divide r by 2. So we need to know

that r is even. Later on, we’ll also need to

know that a to the r over 2 plus 1 is not congruent to 0

mod N. If either of these things fail, we need to pick a

different a in step one. Luckily, there’s at

least a 50% chance you’ll pick a good value for a. So on average, you won’t

have to try too many times. For step three, we’ll

have to do some algebra. Let’s start with

the fact we know. a to the r is congruent to 1

mod N, which, subtracting 1, gives the a to the r minus

1 is congruent to 0 mod N. Saying that something is 0 mod N

is the same as saying that it’s a multiple of N. So there

must exist some integer k such that a to the r minus

1 equals k times N. Since we assumed

r is an even number, we can rewrite it as a to the r

over 2 minus 1 times a to the r over 2 plus 1 equals kN. And since N equals pq,

we’ll replace it with pq. OK, that was kind

of a lot of algebra. I often find it easier to

work through computations like that on my own instead of

watching someone else do it. You’re welcome to pause

here and check the steps. Here’s what happens with the

example where we are trying to find the factors of 35. Since the period of 8 mod 35

is 4, we have 8 to the fourth is congruent to 1 mod 35. So 8 to the fourth minus 1

is congruent to 0 mod 35. Actually, 8 to the

fourth minus 1 is 4,095, but we only care about

its value mod 35. We could rewrite this as

8 to the fourth minus 1 equals k times 35

for some integer k. Again, we could solve for k in

this case, but it’s irrelevant, so I’ll leave it as a variable. Rewrite this as 8 squared

minus 1 times 8 squared plus 1 equals k times p times q where

p and q are the prime factors of 35 that we’re searching for. Step four is the grand finale. I claim that the

greatest common divisor of a to the r over 2 minus 1 and

N is one of the prime factors. Let’s call it p, and the

greatest common divisor of a to the r over 2 plus 1 and

N is the other prime factor. Let’s call it q. Why? The equation a to the r over 2

minus 1 times a to the r over 2 plus 1 equals kpq means that p

must divide one of the factors on the left and q must divide

one of the factors on the left, but they cannot divide the same

factor since that factor would be divisible by N. Why is neither factor

divisible by N? For one, we assumed

a to the r over 2 plus 1 is not congruent

to 0 mod N. For the other, we know r is the minimum value

of x such that a to the x is congruent to 1 mod N. So

a to the r over 2 minus 1 is not congruent to 0 mod

N. Since p and q divide separate factors on the

left side of the equation, we can assume p divides

a to the r of 2 minus 1 and q divides a to

the r over 2 plus 1. So our formulas work. Again, that part contains

some weird algebra arguments. Go ahead and pause to think

about it or rewatch it. So in our example, p is

the greatest common divisor of 63 and 35, which is 7. And q is the greatest

common divisor of 65 and 35, which is 5, which

fortunately is correct. In summary, here’s our steps. Step one– pick a less

than N. Step two– find the period of a

mod N. Step three– well, we don’t need to do all

of the algebra of step three every time since

we know it works. So instead, we’ll use step

three to check that r is even and a to the r over

2 plus 1 is not congruent to 0 mod N. If

either of these things fail, we need to go back to step

one and pick a new value of a. Finally, step four–

let p equal the GCD of a to the r over 2 minus

1 and N. And let q equal the GCD of a to the

r over 2 plus 1 and N. And you’re done. You’ve destroyed

information security. OK, but obviously

there’s a catch since RSA cryptography

still works. Here it is. Step two, finding the

period, takes a long time– in fact, an

exponentially long time. That might make it

seem like we haven’t done a lot by constructing

these four steps, but actually we did. All the steps besides

two are pretty fast. Instead of looking for

a needle in a haystack, we reduced the hard

part to one step– finding the period. And– here’s the big twist– period finding is

precisely the kind of thing a quantum computer is good

at, and on the next episode, we’re going to dive into that. The four steps we just

reviewed are the outline of Shor’s algorithm,

and next time we’ll finish up by learning

how to use a quantum computer to dramatically

speed up step two. Then RSA cryptography

and your bank statements will really be in trouble. See you next time on

“Infinite Series.” Hello, I want to address some

of the comments on our episode about exchanging the

digits of e and pi. First, Joel David Hamkins,

one of the mathematicians whose work is featured

in the original episode, asked a follow up question. He asked, what if

we do not insist that the digits being swapped

come from the same digit place? So you can swap a digit

from anywhere in e with a digit from

anywhere in pi. Well, in this case, you

can make a rational number, and he proves that

in a blog post, which is linked to in the comments. All right, lots

and lots of folks asked about combining

the digits of e and pi algebraically instead

of literally swapping their digits. So can you add, subtract,

multiply, divide the number e and the number pi to

get a rational number? There’s a couple cool famous

examples like e to the pi i plus 1 is equal to 0. That’s Euler’s identity, and

there’s some really silly examples, like e times

pi divided by e times pi is equal to 1, but there’s

also a lot of things we don’t know about when

you multiply and divide e and pi whether you get

rational or irrational numbers. Some of my favorite examples

are these funny almost integers. So for example, pi to the ninth

divided by e to the eighth is really, really, really

close to 10, but it’s not. It’s not the number 10. It just kind of looks like that

if you do the computation out by hand. Also, e to the sixth minus

pi to the fifth minus pi to the fourth is really

close to 0, but it’s not 0. It just kind of looks like it. Finally, Reddles won

the challenge t-shirt for a very complete

answer to the question. If e and pi differ at

infinitely many digits, why is the list of

numbers produced by swapping infinitely many of

their digits uncountably long. Here’s the answer. For each digit that is

different between e and pi, you can either swap it or don’t. Therefore, we can label

a given permutation by listing whether or not

we swapped each digit. If we use 0 to represent doing

nothing and 1 to represent swapping the digit,

then each one of these corresponds to a list

and zeros and ones. Now, they mentioned two

proofs that this list of zeros and ones is uncountable. The first is that it’s in

bijection with the interval 0, 1 written in binary,

and the second is that you can use

Cantor’s diagonalization argument directly on it. Great answer. There were also a lot

of other great answers– way too many for

me to acknowledge. So thanks, guys. They were fantastic. See you next week.

## Kai Kunstmann says:

3:00 Actually, the modulo applies to both sides: "A ≡ X (mod N)" reads "A and X are equivalent, modulo N", i.e. "the remainder of A/N is equal to the remainder of X/N" (and not just equal to X), or (likewise and less ambiguous) "the difference A-X of both sides is a multiple of N". For example, "22 ≡ 7 (mod 5)" is true and implies that 5|22-7 (i.e. 22-7=15 is divisible by 5), but it does not imply that the remainder of 22/5 must be equal to 7.

## Дмитрий Веселов says:

Can someone explain where does 3Mod10 sequence (3.46) comes from? What is the full operation? Do we divide 3 to the power of K by 10 and the sequence is the remainder?

## Chris Courtney says:

You will be assimilated.

## Vincent-Olivier Roch says:

at 3:06 a == x mod n doesn't mean that x is the remainder of a divided by n, but they do have the same remainder. so the right thing to say would be that n divides (a-x). so we could say in that logic that for all integers x y z n, x == y mod n implies that x == y + zn mod n.

For example, 5 == 8 mod 3, but 8 is not the remainder of 5 divided by 3

## Not A Cat says:

I wish I was smart enough to understand any of this…. or that I would pay any attention to math class is high school 😔

## Tushar says:

Excuse me but I have to say you are really beautiful 🙂

## syaondri says:

so the hacking on Summer Wars is true? XD

## Tynan Sigg says:

I don't see how the period-finding step could have a higher complexity than O(n). The period cannot be more than n, so why isn't it simply a matter of checking a^1 through a^n for a power that results in 1 mod n?

## Amir Fayazi says:

These videos are so good

## SuperHddf says:

Thank you sooo fu'king much!!! 🙂 ♥

## Kaustubh Kendurkar says:

If N = p * q then you could create a rectangle using p as length and q as breadth and N as area using computer, you could extend the rectangle until area of rectangle is N and know p and q.

## Miles McGrew says:

All this has taught me, is that while our methods of torture may be inconsistent, it is certainly going to be easier in the long run to just torture whoever we believe has the key. Even from a basic cost benefit analysis, the price of a quantum computer vs a few simple torture tools and someone who is really good with them, is a no brainer, torture wins again.

## smeagle2222 says:

you know ive followed pbs spacetime for about a year or so and always felt i understood it but this i struggle with sooooooooo much more , even by the end of the first minute im like ok back to the start for you .

## James P Schuetze says:

I should have stayed in school.

## Myrmidon says:

Step 1: Check if N is divisible by 2 or 3.

Step 2: Check every odd number greater than 3 to see if it divides N.

Step ~10^50: Profit?

## Nehmo Sergheyev says:

(mon) = (if only counting the remainder after dividing by)

## finn fiction says:

Sounds Like YouTube can brute force those Numbers?

wont a Quantum Computer come in pretty Handy?

## KROOL says:

xCa7+0VGs93gtELETim2keluYmqfLLx8bmqo7d0f62MQoUxlQiD6DUVX/gEpEn//A

59QKfvdyfxeT54+wpjyLJZPcD+8PKnVmEIXCwqB/7TyelwyPZQEDe7JdCS3WMLl3y

MWWN12afnFJQAnsyG/3l0wstaM8ZoqA0GGudAw/Ia2fDS1kn+UUA6uGcQTaCYofWj

ZNNol+hcIpuuXmbXetH/TSa8yvlBFbAc4kIxMD+gn/JoeiqixcbLXkcEalGJ5ucmY

BegSEUCYNwnhwFaU5uYs9WebKqus/Lp96mWG5aW3VAdKX8CVS2/36dhLNmUtvt3jl

5Qn6EkpZbmWU9QNkm9biMZf+wo9ln9sfFm+xHz6KztmAWfebTlRXyFI4b4kiO12yO

DyEeu274RxWDWGnhQvkrByBI9gTqBuo2cscR3UgxgyXHEopGl5Zq2P/n+W2fLATMw

hkZquwBgjlVB0UqfQzG7kZl81JvxWaGQEA1i2LNbXzXz9by1zUKxkD+HvEt9QsR/k

B3AT1o29U/v5+afBqU07RfIaIzOpsLGZQ/avd7H3XbcECogzIk8Uv1gOwDnpJ0mi2

U4n+NtIJJ+vsokBmnJMa3dXqUk0CzpIV29Q8iEAgu1mBWO4zUPf7zcqpL5Y8K9mcT

3GEWPz39cOxnYAvMsYWAEPRaob5u5UpiTk67eVPOX3V77tpzyrf9nGirLGWi4COag

fnURLVFRK4LF7VM6qbxB+bl64v0r5PaEFsil/qqAbDHMNYSDQ4Cal30tcQXfBDXZl

0A/w+6/zIbvLIVKd2Ppi33tqCzRnRlJZS9LIlVx6teywR803NplArp+yiirA9GN2a

7a+lAlI02uZvThrbh33gf158sjvJiwwCuyWNbGiywQYrgq8kG2xdJzS6o9/4MbPFj

Up6UmClZpAXUFTma7wdHMVeKg81tWyQ9SHnA9IcXMiXOiRCVRKnRR7PRHqMdWJszv

cUzQNP31I0HmwB6spAk3Pdz4zXUcSpVyw7736QFzvPgYOhRRpSbx1MeIWEvNVxdYP

68Fx+z0pBKQuuB3cSDnfOfrrFXgmhwX/NDGGD0a4WbrCWjTU+qVbPcZjytxuB5Fc5

SNSHNowZImt1Ux+phh/Hb+svY9LU8Pjrcrv2X5EIoIcIrt7CBs3gHihPH0+vktwkp

7yLVM9LtCsHTnk1GIl7J7VbbgWpRaDuAW2QVn/G7iwy67rhYYivR9rkRvwD5pHtfw

gX2x6jy5MDZ3vjICM1WTWQsGPHK6fidGPmYfeVBphHmtqKz1Grxqk7ux+sWziYiXa

4t7++MqtdwpQPBmTuUcNPTdYKKJbUIaSl2EeXQ9CalgJaQ4WE+rPXWfgoCexVW+7+

oXb5T98NeQLLvb3eE1CeWtdHKIUvd2YxGT2bCQfFDleFERZ9pQ70Rxh6crzp2YKU6

rbkvU5fWJz2TG5aO4zuCE

## mathew shoobert says:

When Explaining MOD 5 it counts 0-1-2-3-4-0 ect is that Wrong??? wouldnt it go 1-2-3-4-5-1-2- ect I mean when doing the powers of 2 mod 7 it goes 2-4-1-2-4-1 Ect but thinking about the mod 5 ….. ahhh dam i think i just answerd my own question… dang… mod 7 only goes to 6 then 0 like 0-1-2-3-4-5-6-0-1 ect so 0 is a possible remainder ….. Yeah … sorry but i typed it so im posting it

## Solarflarecon McCloskey says:

So is GCD HCF???

## Sub says:

Oiler

## Sid says:

what if the number has more than two prime factors, such as 30 = 2.3.5?

## Shylo x Fading 770 says:

my brain hurts

## Jorge C. M. says:

Her: you should check these steps.

Me:

*watches screen nervously*## OpenSourceLiving says:

I do wise she had done this in English

## Ridden Studios says:

gcd(a,n) = 1 are called co primes. Surprised she didn't actually say it. The Affine Cipher is a classic example of this where it only works with co primes.

## Graham Houston says:

surely step 4 takes longer than step 2?

## Compins says:

This. Was perfect.

## sam111880 says:

Nice video i knew this but i thought about another question pertaining to this video on cracking RSA. It is what happens if we load a precalculated database of the periods then just do a look up we could also presort the database. Would this have any major breaking abilities on average for the 512 RSA and other commonly used RSA primes used currently.

## sam111880 says:

This is sort of like rainbow tables for hashed passwords and other things that use dictionary based attacks.. Your really not using this dictionary method as a brute force your just using it to get by the complexity of finding a^r-1 =0 mod n or another words getting around the inverse discrete log problem…Unfortunately i don't currently have the computing power and computer space to test any of these results locally but it sounds plausible that the RSA guys just made the current RSA primes big enough to not be broken by anybody but themselves or companies with huge supercomputers/ databases

## kindlin says:

Your screechy intro is always way louder than the rest of your video.

## Thomas Busse says:

How many large prime numbers are there in the keyspace? With computers all around the world finding them, is a dictionary of large primes being created?

## Steph Escobar says:

She is easily the best non-fiction presenter on youtube. Keep up the good work, PBS. And of course props to Kelsey.

## Tyler Shepard says:

Answer: Use AES… it does not rely on prime numbers at all. It’s quite hard to crack, because it’s addition is mod 2 which ends up being XOR and it’s hard to guess input bits if you know the result of an XOR.

## Tarsha Micola Von Furstenrecht says:

So confusing

## Revaz Eristavi says:

Wow.. I really have to update myself with maths. Good work girl.. Keep it up Bravo..

## Sabbir Ahmed says:

She is cute 😍😍

## Shameer Ahamed says:

Can you please explain this encrypted message

<^C1^H^E5^F^L<^L^F5^E^C^F<^L3^F1^E1^F^C3^K3^L1^@53^@^F

^H^G5^A13^C^F^H;^A5<;^H3;5<^L0^G^L0<35^H^Aj

The decrypted message is

bf4b62e245f6ab6036913a17e68f1a9f

a5c96f71a17f657a1e7c6c75e2e1c4fe47098f3ce579b3fab9ebfa1d81daef93

Probably you are the right person to get the right explanation.

## TwinnedSilver43 On Xbox one says:

i just want to know how to make a table from a cryptography in a grid i can't do i. CAN SOMEONE HELP ME PLZ !!!!!!!!!!!!!!!

## Abdullah Algurashi says:

after research about (a) value in shor algorithem I found it come from this equation:

(q-1)/2

if N = 5*7 = 35 then (a) value will be: (5-1)/2 = 2

So I started with a=2 I found r=12.

2^12 mod 35 = 1

in the video (a) value was 8 and (r) value was 4 and this is mean

8^4 = (2^3)^4 and its equal first value 2^12.

you can try with any example for N U will find (a) value come from (q-1)/2.✌

## regex tex says:

She is so cute. We miss her.

## zog zog says:

Ends with "way too many for me to acknowledge, thanks guys". Two points here. One is that she can't count a simple number. Maths, nah. Arithmetic, not even that. She can't count! Second Point. Note her outfit and the word 'Guys'. Conclusion is this: 'Ok boys, come round to my place, I wont count how many 'guys' cum round'.

## Shay Lempert says:

Came here a few months later.. I am surprised that I understood it this time..

Now I can truly say that shor is a genius, and this video is great!

## Teion M83 says:

Ouch! This was way too much math for me.

## Cyber Crow says:

Wow! So thats how magic looks like.

## Phil Keyouz says:

There is also other mathematical way to find phi(N) without knowing P and Q.

## Compins says:

Alright, I'm back. I kinda don't understand the explanation at 9:52 – 10:06. I don't really see the logic there. I see why it has to be like that, so that we don't up with 1*N = p*q.

Is it

a^(r/2) =/= 0 mod Nbecause we can't geta^(r/2) = 0 mod Nfroma^r = 1 mod N?## Kevin Exit says:

I studied discrete math in high school and regretted not being math or compsci major in uni. I understand about 40% of this. Shor’s algorithm was new to me. I knew Euclidean algorithm. Thank you for this! I will now study number theory for RSA to fully solidify my understanding! Thanks so much PBS giving me direction on where to study next.

## Shane Stevens says:

Loved this episode so much! 👍 Kesley is brilliant!

## YouTubist666 says:

Great explanation. And what a surprise to learn this is Shor's algorithm, which I first heard of in an episode of Big Bang Theory.

## Overkillius says:

Being a musician, modular arithmetic is like crack to me, and it is rare when one of these math videos on youtube actually say something interesting about it and feed my addiction.

so… yeah I need some more please

## Mihai Lazar says:

So you now use Star Trek CommBadge chirps as your sound effects ?

i like that

## Martin Verrisin says:

what do I not get?

– If we already have both a and r and can solve for k… why not just do that?

— Then we will have:

p = k

q = N / k

…why are the last 2 steps needed? This seems easier, fast and I don't see why it doesn't work…

## Edward Williams says:

BitLocker corrupted my boot sequence. I hate Euler ..

## Elcee Michael says:

I am the only one who understand nothing ?

## SoturinTie says:

I've always known math is sexy

## 诚昭曾 says:

Remind me the fear of studying number theory when I was in college.

## Mohit Negi says:

😌😌😌😌😌😌😌😌😌 mathematics..

## Felix Nguyen says:

Is there a formula to calculate the period of a mod n?

## Drexler Altarejos says:

I was kinda confuse with 3^k to the congruence of 3 mod 10

they must have used 3^k mod 10 to avoid the confusion

## Michael Sanders says:

wouldn't the period of any decimal number have a ceiling of 10? i don't understand why that is the Schor's bottleneck. seems finding gcd would have larger complexity.

## JLGaming says:

3:12 It should be that X/N has remainder a…

## SinthTeck says:

But isn't 0 mod N always 0? Why not just say 0?

## hal ise says:

question:

101 to 119 digits first primes

i find last day this funy link:

https://www.alpertron.com.ar/ECM.HTM

x=1;x=n(10^(c+99));c<=20;x

press 'only evaluate'

left number 1 and repated 000000 is eliminated

000267 (101 digits)

000003 (102 digits)

000117 (103 digits)

000129 (104 digits)

000267 (105 digits)

000003 (106 digits)

000079 (107 digits)

000003 (108 digits)

000019 (109 digits)

000457 (110digits)

000007 (111 digits)

000139 (112 digits)

000207 (113 digits)

000099 (114 digits)

000271 (115 digits)

000079 (116 digits)

000093 (117 digits)

000279 (118 digits)

000709 (119 digits)

19 number list 101 to 119 digits first primes only 1 second

question:

if 1001 to 1019 digits first primes:

x=1;x=n(10^(c+10^3-1));c<=20;x

only a few minutes displayed

question:

if x=1;x=n(10^(c+10^12-1));c<=20;x

not calculte on arround the world, any semi conductor super computer or parellel billion computers!

not calculate quantum computer this question!

halogram reader easily!

left 1 and repeat 000000 is eliminated, only meanfull last 36 digits!

trillion+1 to trillion+19 digits first primes ?

if you are a good math man or good math girl, please show me 19 * 36 digits!

## hal ise says:

the prime numbers are not safe! people are crude idiots!

## eto pass says:

Trinity from the matrix move just explained to me how to aproach cryptography =)

## nonameforyouok PeterRodney says:

The solution to factoring any composite integer is equivalent to determining the non-trivial, positive real-value of a variable (k) I call the 'Coefficient of factorization' used in a unique, integer-factorization expression of mine which I've termed the 'Transformula'.

## nonameforyouok PeterRodney says:

If you can figure out a way to determine the non-trivial, positive real-value of a variable (k) I call the 'Coefficient of factorization' utilized in the aforementioned formula, we do not need a Quantum Computer implementing Shor's Algorithm to factor large composite integers! This could settle once and for all the P vs NP question regarding Integer Factorization!

## nonameforyouok PeterRodney says:

Here are 2 mathematical expressions:

1. P= round(.25*(((3+(2*sqrt(2)))^n)+((3-(2*sqrt(2)))^n))^2)-2 (n=positive integer >=1)

2. Factors = sqrt(((1+T(sqrt(P)))^2)+P) +/- T(sqrt(P)) +/- 1 (P=composite integer,T=truncation operator)

The 1st expression above generates Composite integers whose size (no. of digits) grows at an exponential rate with increasing n. The amazing thing about the 1st expression above is that it produces composites that is factorable by the 2nd expression above! Try it! but remember to set the precision for calculation high enough so that the 2 expressions above produce integers as output!

## nonameforyouok PeterRodney says:

For you 'MAPLE' users, here's the code: – (substitute other positive integer values for n!)

> restart:

> Digits:=500:

> n:=50:

>

> P := round(evalf(.25*((3+2*sqrt(2))^(n)+(3-2*sqrt(2))^(n))^2-2));

>

> F1 := trunc(convert((sqrt((1+trunc(sqrt(P)))^2+P)-trunc(sqrt(P))-1),rational));

> F2 := trunc(convert((sqrt((1+trunc(sqrt(P)))^2+P)+trunc(sqrt(P))+1),rational));

>

## Tadesan says:

This video travels the path of a rigorous proof with the casual nature of sightseeing.

By watching it you are seeing more than you are aware of.

Thank you for your thoughtfulness!

PS, I love you!

## Jose Saldivar says:

Kelsey, what is the integral of one over the squared root of a log .(a x), DX How do you do that

## suken_masih says:

can u solve it plz…

11113359471012….

Key is C

## Munteanu Claudiu says:

inspires me, i understand, i love math, i want that math IQ and i want to have a cat

## Dumble Door says:

Thank you for making a non-mathematician understand a complicated subject such as breaking cryptography 👍 Also is prime number product the only way to make reliable cryptography?

## András Fogarasi says:

How to factor huge numbers:

Step 1: Get a computer that will last a trillion years.

Step 2: Factor.

## CubingWithMath says:

thats not how congruency works

## CubingWithMath says:

a mod x = b means if you divide a by x you get b. a congruent b mod x means a and b have the same remainder when dividing by x.

## TIMS3O says:

It is called order, not period.

## OGUZHAN KOSAR says:

Beyoond shweret. Tackling all of the obstacles. Just as it has been done for the e pie video. Great. 👍🏻👏🏻👏🏻👏🏻

## Venkatesh babu says:

Overlay primes.

## Rick H says:

Please see my new Riverside Confession letter hidden message decryption that shows a possible 3 character nickname for the Zodiac Killer. Conventional coding methodology unconventionally applied! Please click on the abstract round humanoid icon to see a short video on my new LoFi YT channel. Also a proposed geometric algorithm for the previously unsolved Ebeorietemethhpiti remainder of the D&B Harden solution to Zodiac's 408 cipher. Thanks.

(Adult true crime content)

## Ciao! says:

great presentation!

## Jakob Michelizzi says:

when you explained modular counting I am confused because in one example you included 0 and in another you didn't. does modular counting include 0 or not?

## Orthodoxforever71 says:

Everything started with Greek mathematicians.Without the Greek geniuses there would be no

Euler,etc

## ⵉⵜⵔⵓⵏⴰⵓⵜ says:

So the only thing keeping RSA cryptography from collapsing is the assumption that computational power won't exceed a certain level.

## K1naku5ana3R1ka says:

1:27 Actually, you only need to check the primes up to the square root of the number being factored; if there were any factors larger than that, then the other factors must all be smaller, and would have been discovered earlier, so you could divide them out and continue to get the full factorization.

## K1naku5ana3R1ka says:

You keep talking about two prime numbers being multiplied together and somehow used as a key, but never explain exactly how that works. I admit that would take a while, but do you have another video explaining how RSA cryptography works?

## 9irep says:

intellect and beauty in one body)

## Siddharth Mahendra says:

Greetings sir i think 3(1,4,7)6(2,5,8)9(0,3,6,9,) .

## trulucy says:

Alright, I will try to be clever and summarize my lack of understanding of the majority of the video in this way: I+am•a^dummy!

## Sourav Dey says:

Very difficult for me…😥😥

## emjackson81989 says:

So, here's a question that may or may not be covered in the next episode: Does Shor's Factorization Algorithm hold even for large numbers that are multiples of n large numbers where n > 2? That is, does it hold for N of the form p*q*r…*z?

## Alessandro Bresci says:

Today we use Elliptic Curves… At least for new keys…

## ve2zzz says:

…Now i understand why buffoons want to defund PBS…

## ve2zzz says:

Hi…

May someone explain me ?

I found this explanation highly interesting… So, i wrote some C for curiosity… Code works, but…

…Finding"r" is waaaaaay longer than brute force factoring…

For example:

Factoring 21583 into 113 and 191 using 8 for "a" required 2660 iterations to find "r" while BF needs 57 iterations for a complete factor,

Another example:

factoring 4661 into 59 and 79 using 19 for "a" required 1131 iterations to find "r" while brute force needs only 30.

What did i do wrong ???ffff

## Swapnil Wankhede says:

Very intersting, I am in 12 class and i am really looking forward to learn this kind of stuff about hacking and cryptography where should i start learing from please suggest and one more thing i really like your english speaking

## Amaryon Bates says:

U lost me at 6:26

## Yano Lavin says:

2:30 : okay… seems a little complicated

2:32 : I'm sorry what?

## George Andrews says:

I wrote an encryption method for messages that quantum computers can’t break.

It doesn’t use keys and doesn’t allow you to know exactly when a encoded message stops or starts in the output.