It wasn't very well explained. Shor's Algorithm is just quantum factoring. It helps to understand what a "conventional" computer IS mathematically and why computers were invented in the first place. Not all cryptography is affected just those that heavily reply on prime factorization like RSA which is used for public key cryptography. Further even if you had a quantum computer that doesn't mean it'd actually be any faster then a super computer at brute forcing the key. It just that there is a quantum algorithm with much lower time complexity that can break prime factors. Not only does the quantum computer need at least as many qbits as the keys bits (this website uses a key with 2048 bits) but then your operations need to actually be fast and reliable which they won't be even after quantum computers are ubiquitous. Large scale parallel GPU farms are probably still a bigger threat really.
@@silentinferno2382 So if I try to find Micheal Stevens saying prime numbers for 3 hours 1000h complilation I am not going to get a video that has significantly more said numbers per video? Or a reaction video to this 3 hour video that sais the numbers along side Micheal.
I had to slow it to 0.75 even tho I speed upto 2x other plain verbal videos. Here it's a problem because he's writing much faster than what he is saying.
The number 16129 is one I will recognize instantly. If you have base 210 (2×3×5×7), and you want the square of prime following square of following prime after last prime in base 210, this is the number you get. I've seen this number so many times… For similar purpose. Faktoring. Not big numbers, but a lot of them (at once). Not using super effective algorithm, but my own. Why? I was bored once on job interview. And I asked myself „what is the chance of specific prime being the lowest factor of any given number?“, after which I came up with theory. I've not stopped there. I went deep, into numbers and factoring. Found unexpected things and realized that expected things were in fact stupid.
Don't feel bad, even with a Physics degree there's a couple of parts I'm still hazy on. These videos, in my opinion, aren't necessarily aimed at a general target audience, but more-so making the explanation (not quite fully explained ofc) available to someone in a concise, and clear, visual medium. Then, anyone at the appropriate levels of understanding for this video, can watch it and grasp what they otherwise perhaps could not. Doesn't mean you can't read up on the topic of quantum decryption though if you want to!
This video was very clear and helpful. The previous video left a lot of open questions, but this one was excellent. Still not sure I understand exactly how the QFT and remainder operations work, but knowing those are the functions being implemented means that can be treated as a separate issue. Great job!
3:30 I've had moments like this in calculus where I realized that I either forgot to simplify something or simplified it too much and have to start over, I can't imagine how frustrating it is in Quantum Mechanics or Linear Algebra
Application: Classical Part of Shor's #Algorithm q=GCD[P,x^2+m] (Eq 4.) Title: DNA Of Prime Numbers & New Factorization Method Noted: factorization method (Improvement of the quadratic sieve and application of Legendre’s conjecture) P=n^2+m (Eq 1.) P=pq (Eq 2.) p=GCD[P,x^2+m] (Eq 3.) or q=GCD[P,x^2+m](Eq 4.) Where: n=Floor[P^.5] (Eq 5.) m=P-n^2 or Mod(P,n^2) (Eq.6.) Range: x={0,1…n } (Eq 7.) Overview: Theorem: There are many infinite natural Integers in the form of P=n^2+m. (Eq 1.) Legendre’s conjecture: Does there always exist at least one prime between consecutive perfect squares? n^2 < Prime
This was from ages ago, but at least in the video, he used 101 and 127 which are both prime, so I’m not sure if “g” ought to be a prime number and that was glossed over, or if that’s possible here.
I tested this out and, yes, you can do this but I'm not sure how advantageous it really is.. There's still a solid chance you'll wind up with the case where your "solution" just yields 1 and the number you're trying to factor. But it clearly can work. 729 (27²) is a good example. I got 1449 for p, instead of taking p/2 you just calculate GCF(27¹⁴⁴⁹ ± 1, 314191) and out pop the factors. (And, obviously, g doesn't have to be prime, any integer >=2 can be used) This is all on a classical computer of course. No idea what happens when QC gets involved.
It is 2019 so he swapped it for 19. Or did he? 1+9 is 10. 10 isn't a prime number, is he trying to tell us that he's next video going to be "Top 10 non-prime numbers that mathematicians hate"?
Easier summary: Basically, make a guess, start finding powers of that guess, convert those into a simplified version of a wave (basically, decompose a wave into frequencies), and collapse the superposition of all of those computations. Because the collapsed superposition is random, you need to get a few samples before you find the factor. Factoring numbers is hard, but finding the common factor of two numbers is easy (it's called Euclid's algorithm). It's not good for breaking giant numbers composed of two primes because the chances of you finding two numbers sharing the same prime is incredibly small. Shor's algorithm improves those chances and gets you better probabilities, so you can actually find a common factor that isn't one.
That's not exactly right, since the number of qubit states isn't usually an exact multiple of the period, so after you take the QFT you only get approximations to the frequencies. You have to use continued fraction expansion to recover the period after you take the measurement then, and you're pretty likely to measure a suitable approximation that you can recover the period.
If you're talking about the ones that look like | x 》 (please pardon the double arrow, my phone doesn't have every symbol it should), then those are called kets, and they are a preferred way of representing vectors.
Would you explain how you use Euclid's algorithm for determining GCD(314191,127^8694) please. I am quite sure Euclid's Euclid's algorithm would never work and do not understand how the improvements made to the algorithm (to deal with such ridiculously large numbers) work.
In this scenario, just Euclid's algorithm is enough. I typed "gcd 314191 (127^8694+1)" into Haskell (or anything else with a bignum library) and I get a result immediately. But you can read about the improvements by looking up modular exponentiation by squaring. It's just based on properties of modular arithmetic, which are pretty intuitive if you play with them on small examples.
Euclid's algorithm has no limitations on the size of the input numbers, that just doesn't make sense. If you're talking about the hardware or software limitations, you can always use a suitable library to handle those large numbers (like BigInteger in Java or break_infinity.js for JavaScript). Mathematical packages and programming languages support big numbers by default, there's no trouble. So, let's see what is Euclid's Algorithm exactly. In pseudocode, its very simple: Algorithm GCD(number1, number2): 1. If number2 is 0 return number1 2. If not, return GCD(number2, number2 mod number1) Now an explanation. For additional context, by "number" I will mean a positive integer. Given two numbers n1 and n2, their gcd is the largest factor that both of the numbers have. All numbers are divisible by 1, so its always the smallest possible gcd of any two numbers, and also all numbers have a unique prime factorization according to the fundamental theorem of arithmetic. Now, lets say n1 mod n2 means "the remainder when n1 is divided by n2" (integer division). Let's say that n1 = g * p1, n2 = g * p2, where p1 and p2 are coprime (have no prime factors in common). Then, by definition, gcd(n1, n2) = g, the numbers both share the factor g. Notice, that if we take n1 mod n2 so we take the remainder when n1 is divided by n2. Let's say n1 = k*n2 + m, m < n2. Then m is the remainder mod n2. Substitute n1 = g*p1, n2 = g*p2. g*p1 = k*(g*p2) + m expand brackets g*p1 = g*k*p2 + m We get a multiple of g as a sum of a multiple of g and some number m. That is only possible when m itself is a multiple of g. Let's say m = g*p3. It'll simplify to g*p1 = g*(k*p2 + p3). So, the remainder is also a multiple of g. Therefore, we've just proven, that if n1 and n2 share the factor g, then n1 mod n2 and n2 will also share that factor g. We can use this identity, acknowledging that n1 mod n2 is always smaller than n2 by definition, to simplify the task of finding gcd into much easier division problems. gcd(n1, n2) = gcd(n2, n1 mod n2). And when we've reached 0, it means that some value of n1 and n2 are multiples or divisors of each other. Yeah, when n1 mod n2 = 0, then n1 = k * n2. So the "m" is 0. And then we know, by the chain of simplifications, that the common factor g was always a factor of both n1 and n2. If n1 = k*n2 and n1 = g*p1, n2 = g*p2. g*p1 = k*g*p2 divide by g p1 = k*p2, where p1 >= 1, k >= 1, p2 >= 1 by definition of positive integers, and p1 is coprime to p2 by our definition. Then, p2 would have to be one, because otherwise p1 would be a nontrivial multiple of p2 (p1 = k * p2, p2 > 1), which is impossible, because p1 and p2 are coprime. So, p1 = k*1. p1 = k. g*p1 = k*g. But n1 = g*p1, n2 = g*p2, we've proven than p2 = 1. This means n2 = g, n1 = g*p1. The next step of the gcd is GCD(n2, n1 mod n2). We've determined that n2 = g, n1 mod n2 = 0. So, we can just return the g and that's the common factor. The only way for n2 to equal to g is that n1 mod n2 = 0. This is the needed theory. Let's do an example. GCD(35, 14): Second number is not zero, doing 35 mod 14. 35 = 2 * 14 + 7. Remainder is 7. Doing GCD(14, 7). Second number is not 0, doing 14 mod 7. 14 = 2 * 7 + 0. Remainder is 0. Doing GCD(7, 0). Second number is 0, returning 7. The GCD is 7. Another example. GCD(2, 17): Second number is not 0, doing 2 mod 17. 2 = 0*17 + 2. Remainder is 2. Doing GCD(17, 2). Second number is not zero, doing 17 mod 2. 17 = 8*2 + 1. Remainder is 1. Doing GCD(2, 1). Second number is not 0, doing 2 mod 1. 2 = 2*1 + 0. Remainder is 0. Doing GCD(1, 0). Second number is 0, returning 1. The answer is 1. You can check other cases. GCD(a, b) = GCD(b, a mod b), do until you reach 0 = a mod b, and then the answer is b. This algorithm is very efficient. It requires few steps, around log(n), where n is the smaller number out of the two, if I remember correctly, you can see the Wikipedia page to learn more. The last part: how to actually calculate 127^8694±1. Actually, you don't need to. As you have noticed, the algorithm reduces the problem mod some other number, in that case, being 314191. So we just need to know 127^8694±1 mod 314191, because if we don't take mod that will still be the first step of the algorithm. For that we can use an effective modular exponentiation algorithm like the square and multiply algorithm. Suppose we need to find a^b mod c. a^b is a huge number, but a^b mod c is less than c by definition. So, we don't want to calculate the exponentiation step by step and store everything. We can take mod c every single step to reduce our numbers to something more manageable. That won't change the answer. a * a * a (mod c) = (a * a (mod c)) * a (mod c). a^3 (mod c) = (a^2 mod c)*a (mod c). I won't get into the details why that is true, but you can search about the product and power rules of modular arithmetic. Alright, now we know to take mod every step, time to talk about the steps. As we supposed, we need to find a^b mod c. Let d = a, after the operations d will become the answer. Then, write out the binary expansion of b. Then, for every bit to the right of the most significant bit, from left to right, do the following: 1. If that bit is a zero, square d, mod c. 2. If that bit is a one, square d, multiply that by a, mod c. Let's see why that's true. Out result was initially d = a = a^1. Each time we squared d, we multiplied its power by 2 (if d at some point was a^k, then d^2 = (a^k)^2 = a^2k). Each time we multiplied d by a, we added one to its exponent (if d = a^k then d*a = a^k * a = a^(k + 1)). We can reach any exponent we want by doing the binary expansion of it. In binary, squaring the number is the same by multiplying the exponent by 2, which in binary is a simple left shift. Multiplying by a is simply adding one to the power. That's why we did every single bit to the right of the most significant bit, we were basically building the needed exponent in binary. Originally, it was 1 (d was = a = a^1), so the most significant bit is already accounted for. Example: 3^11 mod 5 11 in binary - 1011. d = a = a^1 = 3 Ignoring the most significant bit. The next one from left to right is a zero. d^2 = 3^2 = 9 9 mod 5 = 4 d is now = 4 Notice that the power of a that d is is now 2, in binary it's 10, we've done a left shift of one bit. The next bit is 1. d^2 = 4^2 = 16 16 mod 5 = 1 d is now = 1 d*a = 1*3 = 3 3 mod 5 = 3 d is now = 3 The exponent of a in d in binary is now 5 (it was two, we multiplied it by 2 by squaring the number and added one by multiplying b by a) 5 in binary is 101. The next (and the last) bit is 1. 3^2 = 9 9 mod 5 = 4 d is now = 4 4 * 3 = 12 12 mod 5 = 2 d is now = 2 Notice that the exponent now is eleven, just as we wanted, because its 5*2 + 1 = 11. So, the result is 2. 3^11 mod 5 = 2. This "square and multiply" algorithm is also very efficient, is requires n-1 steps (at the worst case n-1 square operations, n-1 multiplications by a and 2n-2 mods) where n is the amount of binary bits in the power/exponent you're trying to calculate (mathematically speaking, log2(exponent)) I hope you learnt something new today! :D
but what would happen if you encrypt your second guess with the superposition of all the multipliers of p/2. Then you just substitute all the factors of the encrypred superposition multipliers in your other encrypted factors of p to get the same result, right?
*Core Insight* It is very easy to calculate GCD of any 2 large unequal positive integers, and the result is always a factor of both, one of which being the composite number of your interest. Given any factor of your composite numbers, there exist infinite multiples of this factor and you have to find only 1 of them to then use in GCD to get this unknown factor. Through multiple attempts, Shor's algorithm mainly searches for any one of the many "other large positive integer" so that GCD can be used to get at least 1 factor of your composite number. In each iteration, it generates a random positive integer "a" and computes the positive integer period "r" (using QFT for quantum speedup) such that if r is odd (bad luck) then retry with new "a" otherwise you got lucky in this iteration. Simply check if GCD > 1 and you got your non-trivial factor of the composite number of your interest.
I think it's worth pointing out that the final quantum fourier transform doesn't just give a superposition of 1/p, 2/p, ...exactly. Instead, it gives a superposition of integers from say 0 to N-1 where N=2^n, n being the number of qubits representing the number (so N possible states). The states with the largest amplitudes are those integers closest to N/p, 2N/p, 3N/p, and so on. It is important to note that there are (possibly) non negligible probabilities that other nearby integers are measured instead, and that we need to divide this measurement by N to get a multiple of 1/p (or at least an approximate multiple of 1/p). You can calculate the whole QFT yourself if desired, but you will find that the probability of measuring integer x is proportional to roughly sin^2(pi*f*ceil(1/f)*x)/sin^2(pi*f*x) with frequency f = p/N (and ceil is the ceiling function). This indeed has peaks around N/p, 2N/p, ... which can be seen by considering its envelope csc^2(pi*f*x) (also here I am ignoring the special case of x=0 which needs to be summed differently in the QFT)
At 3:00, you say that you measure the same state |1/4347⟩ + |2/4347⟩ + ... multiple times to get several of the basis vectors so you can find their common factor. Then you have to prepare that state multiple times. But you got r = 71426 randomly at 1:39. Doesn't that mean that you have to force the state to collapse into r = 71426 all subsequent times? Is that what you do?
Within the conceptual framework depicted in the video, the point is that the actual value of r doesn't matter, in that the level sets of g^x will always be of the form {x,x+p,x+2p,...} and the p will be the same no matter which r you got. But in a real scenario where you have a finite (but sufficient) number of qubits, this isn't actually what happens, and instead you have some additional work to do to extract the period after that step. The Wikipedia article talks about the details.
I am currently trying to figure out a factoring method that a regular computer could use and recently discovered the Euclidean Algorithm by myself playing around with remainders.
When I go through a hard time with my thesis and think I am dumb and worthless, I look for videos like this to read the comment section. Seeing people saying that they don't understand makes me feel clever for a few minutes...
how to find the superposition of one number? like in 1:25 it says if we start with a superposition of all the numbers up to 314191, how do you find it? if there is a video explaining it, please tell me.
oh extra thing which you could have used to not have to do another trial. 4347 may not be even, but it is divisible by 3. We know how to factorise x^3 - 1, so you could have checked common factors of x-1 and x^2+x+1 with 314191, where x = g^(p/3), and p/3 = 4347/3 = 1449, for g = 101. You would have found x-1 gives 829 and x^2+x+1 gives 379 as greatest common divisors. Even in general, x-1 is always a factor of x^n - 1, so if we find n is a small divisor of p, we always have an easy one to check for common factors, namely g^(p/n) - 1.
Please can someone help? (4 pts) A 30.0 kg child sits on one end of a long uniform beam having a mass of 20.0 kg, and a 40.0 kg child sits on the other end. The beam balances when a fulcrum is placed below the beam a distance 1.10 m from the 30.0 kg child. How long is the beam? A)2.20 m B)1.98 m C)1.93 m D) 2.07 m E)2.12 m
There are currently 42 comments, that's cool. Great video, this answered my main question from the last video. It was a little undersatisfying because I didn't follow along on paper or with a calculator, but that's my fault not yours.
Woah. That's a crazy complex way of getting factors. My question was why just finding the factors by going up the number line isn't faster, but then I realized that it's because the number in the video is MUCH shorter than the real encryption numbers. The actual encryption numbers strength lie in the amount of time it takes to crunch the numbers because they are so long. This quantum algorithm is better because it crunches far fewer total calculations while being able to do most of the calculations it needs to at the same time instead of linearly. Regular computers couldn't do this calculation in a timely manner because they would be doing the quantum part linearly. So, a regular computer might crunch (for example, these are random stats for illustration) thousands of numbers millions of times running through the calculation traditionally, but a quantum computer would crunch simultaneous sets of thousands of numbers a few times. I think?
So what your saying is "in order to solve for P", MAGIC HAPPENS (T=3:56) Can you do a video on 'How to actually solve for P'; Also a brief explanation of how RSA uses co-primes would be awesome. Thanks I really do like your lectures
I still don't know my "times tables" from primary school by heart ... how do I understand these videos, and most importantly, why do I find this actually interesting.
Kind of, yes, but also not exactly. Since we don't know x, and you'll get random results from the superposition, it's far from trivial to figure out p. It's much easier when you're only getting multiples of one specific number (1/p).
@@wangamanga2128 that's cool. i'm the kind of person who can find possibly everything interesting as long as I can understand it i haven't studied maths since high school. but I have a lot of hobby math yt channels that i watch. i have majored in CS engineering (without maths) i really do have a lot of respect for people who are in research. that I am being 100% honest. i plan to go for masters and PhD in future
Another detail you glossed over: the Euclidean algorithm step you need to do in this problem is "anomalously cheap" compared to the size of the numbers because the big number is given as a known offset from a known power of a not-so-huge number. This means you can do modular exponentiation and thus keep your numbers from ever being any bigger than the square of the smaller of the given numbers. If this weren't the case and you had to actually work with, say, the binary expansion of 127^(8694)+1, then you would be better off just doing trial division by primes up to floor(sqrt(314191))=560.
So modular exponentiation is the key to calculating the GCD fast? I was already wondering about that. Using traditional Euclid's algorithm on 127^(8694)+1 and some other large number would take billions of years.
@@ericvosselmans5657 Yes. Following along with the video, the first Euclid algorithm step (which is the only one involving a number way bigger than the number you're trying to factor) is to get (127^8694 + 1) % 314191. The middle bit can be done using modular exponentiation by squaring; you record the remainders when dividing 127,127^2,127^4,127^8,...,127^8192 by 314191 and then multiply the ones that correspond to 1s in the binary expansion of 8694, so the exponents of 8192, 256, 128, 64, 32, 16, 4, and 2. Throughout that process you take remainders at each step, which keeps the numbers you're actually working with from getting any bigger than 314191^2.
luckily there's an easy way to check if you understood all this: grab two 3-digits primes, multiply them and try to factor the result with this method. If I had a lot of NRG I would surely do it
I understood all of those words separately
Lucky you haha
My brain is fire how did you do it
Then you've measured the quantum state of this video. Congrats! You managed the filter all the waveforms by destructive interference
I guess this is one of those 5 minute videos that I have to watch for an hour to understand
Szanyi Atti lost me after 1 min and a half as well...
Szanyi Atti it’s closer to 6 minutes (sorry just had to say)
@@halo_halo9659 I thought that I should write 6 minute video because that would be more true, but 5 minute video sounded better.
It wasn't very well explained. Shor's Algorithm is just quantum factoring. It helps to understand what a "conventional" computer IS mathematically and why computers were invented in the first place. Not all cryptography is affected just those that heavily reply on prime factorization like RSA which is used for public key cryptography. Further even if you had a quantum computer that doesn't mean it'd actually be any faster then a super computer at brute forcing the key. It just that there is a quantum algorithm with much lower time complexity that can break prime factors. Not only does the quantum computer need at least as many qbits as the keys bits (this website uses a key with 2048 bits) but then your operations need to actually be fast and reliable which they won't be even after quantum computers are ubiquitous. Large scale parallel GPU farms are probably still a bigger threat really.
Yep!
Protip: watch at 0.25 speed. You won't understand anything, just like now, but at least you get to hear your computer make some fun sounds!
1 hour + google additional info + understanding additional info = 314191 seconds / 60 ~= 5 236,516 minutes / 60 ~= 87 hours. Simple.
had to watch at 0.0625 speed
you just wanted to see how many numbers you could say in a single video
I know, what a show-off!!😉
Micheal Stevens said prime numbers for 3 hours.
@@silentinferno2382 You really scratched just the surface what you can find in youtube.
@@RanEncounter this was just in comparison. And its more realistic than many of the videos you are trying to describe.
@@silentinferno2382 So if I try to find Micheal Stevens saying prime numbers for 3 hours 1000h complilation I am not going to get a video that has significantly more said numbers per video?
Or a reaction video to this 3 hour video that sais the numbers along side Micheal.
What a fun coincidence. This video was published just one day after I had to implement Shor’s algorithm for my quantum computing class at university.
"Quantum computing class"? What do you study?
@@TheVoidPhantom Nice to know! Thank you and good luck in your studies.
I just realized your university offers online Russian language courses, thanks for the link!
I understood it completely but I like apple pie more.
I would like cake
I believe the video said there were many pies.
What was it you understood completely? I'm too focused on this apple pie.
@@OrangeC7 3.14
@@bolton368 The cake is a lie
This example makes the original video make much more sense! Thanks!
Yes, I was wondering how the hell the QFT worked!
@@baileyridley8344 ikr
Instruction is unclear, accidentally generated wormhole to the pie dimension.
How is that a bad outcome?
αηδγ ςλαη, what's your name supposed to be?
andy clan?
in Greek it's pronounced aeethwh slaee
The pie-th dimension? Haha
Oh no the pie dimension is filled with human eating pies
@@BankruptGreek You're different aren't you? I can tell by your.. comment
Great! Scrambled brains for breakfast. Now if I could figure out how to tie my slipons I could walk the cabbage. Anyone got coffee? And aspirin?
Old boy you gotta get them sketchers.
You're doing better than I...I tried to tie my cabbage and walk the coffee
Your comment and the walking string bass gives me scrambled brains all over my face.
I've got a quantum superposition of coffee and aspirin (and also, for technical reasons, loratadine). You could measure that and see if it helps...
These kinds of worked out examples are so great. Keep it up!
One of the few video channels that I don't need to speed up, lmao nice one
I had to slow it to 0.75 even tho I speed upto 2x other plain verbal videos.
Here it's a problem because he's writing much faster than what he is saying.
The number 16129 is one I will recognize instantly.
If you have base 210 (2×3×5×7), and you want the square of prime following square of following prime after last prime in base 210, this is the number you get.
I've seen this number so many times…
For similar purpose. Faktoring. Not big numbers, but a lot of them (at once). Not using super effective algorithm, but my own.
Why? I was bored once on job interview. And I asked myself „what is the chance of specific prime being the lowest factor of any given number?“, after which I came up with theory. I've not stopped there. I went deep, into numbers and factoring. Found unexpected things and realized that expected things were in fact stupid.
504. 3125. Isn’t 403. 3125 got to be somewhere? Maybe 625 too? Glad others can understand that pony.
Yes I can understand this video very well before the point it started everything after that is me at 3:30
Breathe. Don't have a stroke
You want a video with 100M views? Do one about UA-cam's algorithm. LOL
This is a really great follow up to the previous video. Really helps to illustrate just how powerful this algorithm is.
I'm just gonna pretend I understand a thing of what he is saying
Thank God I'm not the only one LOL
Don't feel bad, even with a Physics degree there's a couple of parts I'm still hazy on. These videos, in my opinion, aren't necessarily aimed at a general target audience, but more-so making the explanation (not quite fully explained ofc) available to someone in a concise, and clear, visual medium. Then, anyone at the appropriate levels of understanding for this video, can watch it and grasp what they otherwise perhaps could not. Doesn't mean you can't read up on the topic of quantum decryption though if you want to!
Did you watch the first part?
This video was very clear and helpful. The previous video left a lot of open questions, but this one was excellent. Still not sure I understand exactly how the QFT and remainder operations work, but knowing those are the functions being implemented means that can be treated as a separate issue. Great job!
3:30 I've had moments like this in calculus where I realized that I either forgot to simplify something or simplified it too much and have to start over, I can't imagine how frustrating it is in Quantum Mechanics or Linear Algebra
Application:
Classical Part of Shor's #Algorithm
q=GCD[P,x^2+m] (Eq 4.)
Title: DNA Of Prime Numbers & New Factorization Method
Noted:
factorization method (Improvement of the quadratic sieve and application of Legendre’s conjecture)
P=n^2+m (Eq 1.)
P=pq (Eq 2.)
p=GCD[P,x^2+m] (Eq 3.)
or q=GCD[P,x^2+m](Eq 4.)
Where:
n=Floor[P^.5] (Eq 5.)
m=P-n^2 or Mod(P,n^2) (Eq.6.)
Range: x={0,1…n } (Eq 7.)
Overview:
Theorem:
There are many infinite natural Integers in the form of P=n^2+m. (Eq 1.)
Legendre’s conjecture:
Does there always exist at least one prime between consecutive perfect squares?
n^2 < Prime
Couldn’t you use a perfect square as your “crappy guess” so that even if p is odd, g^(p/2) is still an integer?
This was from ages ago, but at least in the video, he used 101 and 127 which are both prime, so I’m not sure if “g” ought to be a prime number and that was glossed over, or if that’s possible here.
@@Fuzbo_ We're carrying out prime factorisation here (as far as I know) hence, "g" would be required to be a prime number
I tested this out and, yes, you can do this but I'm not sure how advantageous it really is.. There's still a solid chance you'll wind up with the case where your "solution" just yields 1 and the number you're trying to factor.
But it clearly can work. 729 (27²) is a good example. I got 1449 for p, instead of taking p/2 you just calculate GCF(27¹⁴⁴⁹ ± 1, 314191) and out pop the factors.
(And, obviously, g doesn't have to be prime, any integer >=2 can be used)
This is all on a classical computer of course. No idea what happens when QC gets involved.
Even if you can, the problem just becomes factoring the square root of that thing. Not that useful..
@@theoreotically or a number that shares factors
When people make videos to try to look smart than to inform. The smart person here is Peter Shor.
Found the video really helpful! I would highly recommend watching this for starters before formally learning Shor's algorithm in class.
I don't understand your videos for most of their part but I just like to watch them. They are like poems of numbers.
4:36 I can have my pie, but can I eat it too?
Answer: yes, because of superposition
31419 looks like missing out some digits from decimal notation of pi
That's how he picked the number for this example 🦄
Technically that could be said for any number (probably).
It is 2019 so he swapped it for 19. Or did he? 1+9 is 10. 10 isn't a prime number, is he trying to tell us that he's next video going to be "Top 10 non-prime numbers that mathematicians hate"?
@@HedronProduction Conspiracy confirmed.
I think what OP meant is we’re missing a 5 in there. 3.14159
minutephysics now has become into minutecomputations
Well this is a nice treat.
Also, when’s the relativity series continuing?
WE NEED MORE C
It probably wasn't very popular.
There's not much to add, really
Relatively soon, I'd say.
minutephysics: shor's algorithm
me: haha numbers go brrrr
minutephysics: *pie*
me: PIE
Great video, directly answered all the questions I had from last video :)
1 minute in, and I'm already asking myself why the computer can make golf ball waffles
Easier summary: Basically, make a guess, start finding powers of that guess, convert those into a simplified version of a wave (basically, decompose a wave into frequencies), and collapse the superposition of all of those computations. Because the collapsed superposition is random, you need to get a few samples before you find the factor.
Factoring numbers is hard, but finding the common factor of two numbers is easy (it's called Euclid's algorithm). It's not good for breaking giant numbers composed of two primes because the chances of you finding two numbers sharing the same prime is incredibly small. Shor's algorithm improves those chances and gets you better probabilities, so you can actually find a common factor that isn't one.
The one thing that bothers me is why wasn't the original product 314,159? That would make it much closer to π⋅10⁵.
Because that is a prime number.
@@thorr18BEM Thank you!
This was so complex but you made me understand it so you did a good job
This is one of those videos that feel ten times as long as it actually is
Really outstanding explanation and presentation!
Math is dark and full of terrors.
Luckily minutephysics is here to shine a tiny little light to it. Yay!
What do we say to encryption? Not today
Play it at 0.75X it will be way more understandable and easy to follow him
Nice follow up to the previous video. Much clearer now.
Amazingly concise and lucid explanation.
Great work. One of the best explanations I have seen.
That's not exactly right, since the number of qubit states isn't usually an exact multiple of the period, so after you take the QFT you only get approximations to the frequencies. You have to use continued fraction expansion to recover the period after you take the measurement then, and you're pretty likely to measure a suitable approximation that you can recover the period.
These videos were the best you ever created
What are those operators you use? Where does one learn all that?
If you're talking about the ones that look like | x 》 (please pardon the double arrow, my phone doesn't have every symbol it should), then those are called kets, and they are a preferred way of representing vectors.
Deep dive into Wikipedia by searching for bra-ket notation
We should have got a free pie while watching this video
yes of course
i agree with you
Would you explain how you use Euclid's algorithm for determining GCD(314191,127^8694) please. I am quite sure Euclid's Euclid's algorithm would never work and do not understand how the improvements made to the algorithm (to deal with such ridiculously large numbers) work.
Neither do I.
In this scenario, just Euclid's algorithm is enough. I typed "gcd 314191 (127^8694+1)" into Haskell (or anything else with a bignum library) and I get a result immediately. But you can read about the improvements by looking up modular exponentiation by squaring. It's just based on properties of modular arithmetic, which are pretty intuitive if you play with them on small examples.
@@Latronibus thanks again! I will! I am very curious how these things work!
Euclid's algorithm has no limitations on the size of the input numbers, that just doesn't make sense. If you're talking about the hardware or software limitations, you can always use a suitable library to handle those large numbers (like BigInteger in Java or break_infinity.js for JavaScript). Mathematical packages and programming languages support big numbers by default, there's no trouble.
So, let's see what is Euclid's Algorithm exactly.
In pseudocode, its very simple:
Algorithm GCD(number1, number2):
1. If number2 is 0 return number1
2. If not, return GCD(number2, number2 mod number1)
Now an explanation. For additional context, by "number" I will mean a positive integer.
Given two numbers n1 and n2, their gcd is the largest factor that both of the numbers have. All numbers are divisible by 1, so its always the smallest possible gcd of any two numbers, and also all numbers have a unique prime factorization according to the fundamental theorem of arithmetic.
Now, lets say n1 mod n2 means "the remainder when n1 is divided by n2" (integer division).
Let's say that n1 = g * p1, n2 = g * p2, where p1 and p2 are coprime (have no prime factors in common). Then, by definition, gcd(n1, n2) = g, the numbers both share the factor g.
Notice, that if we take n1 mod n2
so we take the remainder when n1 is divided by n2.
Let's say n1 = k*n2 + m, m < n2.
Then m is the remainder mod n2.
Substitute n1 = g*p1, n2 = g*p2.
g*p1 = k*(g*p2) + m expand brackets
g*p1 = g*k*p2 + m
We get a multiple of g as a sum of a multiple of g and some number m.
That is only possible when m itself is a multiple of g. Let's say m = g*p3. It'll simplify to g*p1 = g*(k*p2 + p3). So, the remainder is also a multiple of g.
Therefore, we've just proven, that if n1 and n2 share the factor g, then n1 mod n2 and n2 will also share that factor g.
We can use this identity, acknowledging that n1 mod n2 is always smaller than n2 by definition, to simplify the task of finding gcd into much easier division problems.
gcd(n1, n2) = gcd(n2, n1 mod n2).
And when we've reached 0, it means that some value of n1 and n2 are multiples or divisors of each other.
Yeah, when n1 mod n2 = 0, then n1 = k * n2. So the "m" is 0.
And then we know, by the chain of simplifications, that the common factor g was always a factor of both n1 and n2. If n1 = k*n2 and n1 = g*p1, n2 = g*p2.
g*p1 = k*g*p2 divide by g
p1 = k*p2, where p1 >= 1, k >= 1, p2 >= 1 by definition of positive integers, and p1 is coprime to p2 by our definition.
Then, p2 would have to be one, because otherwise p1 would be a nontrivial multiple of p2 (p1 = k * p2, p2 > 1), which is impossible, because p1 and p2 are coprime.
So, p1 = k*1. p1 = k.
g*p1 = k*g.
But n1 = g*p1, n2 = g*p2, we've proven than p2 = 1.
This means n2 = g, n1 = g*p1.
The next step of the gcd is GCD(n2, n1 mod n2). We've determined that n2 = g, n1 mod n2 = 0.
So, we can just return the g and that's the common factor. The only way for n2 to equal to g is that n1 mod n2 = 0.
This is the needed theory.
Let's do an example.
GCD(35, 14):
Second number is not zero, doing 35 mod 14. 35 = 2 * 14 + 7. Remainder is 7.
Doing GCD(14, 7). Second number is not 0, doing 14 mod 7. 14 = 2 * 7 + 0. Remainder is 0.
Doing GCD(7, 0). Second number is 0, returning 7.
The GCD is 7.
Another example.
GCD(2, 17):
Second number is not 0, doing 2 mod 17. 2 = 0*17 + 2. Remainder is 2.
Doing GCD(17, 2). Second number is not zero, doing 17 mod 2. 17 = 8*2 + 1. Remainder is 1.
Doing GCD(2, 1). Second number is not 0, doing 2 mod 1. 2 = 2*1 + 0. Remainder is 0.
Doing GCD(1, 0). Second number is 0, returning 1.
The answer is 1.
You can check other cases. GCD(a, b) = GCD(b, a mod b), do until you reach 0 = a mod b, and then the answer is b.
This algorithm is very efficient. It requires few steps, around log(n), where n is the smaller number out of the two, if I remember correctly, you can see the Wikipedia page to learn more.
The last part: how to actually calculate 127^8694±1. Actually, you don't need to. As you have noticed, the algorithm reduces the problem mod some other number, in that case, being 314191. So we just need to know 127^8694±1 mod 314191, because if we don't take mod that will still be the first step of the algorithm.
For that we can use an effective modular exponentiation algorithm like the square and multiply algorithm.
Suppose we need to find a^b mod c.
a^b is a huge number, but a^b mod c is less than c by definition. So, we don't want to calculate the exponentiation step by step and store everything.
We can take mod c every single step to reduce our numbers to something more manageable. That won't change the answer.
a * a * a (mod c) = (a * a (mod c)) * a (mod c).
a^3 (mod c) = (a^2 mod c)*a (mod c).
I won't get into the details why that is true, but you can search about the product and power rules of modular arithmetic.
Alright, now we know to take mod every step, time to talk about the steps.
As we supposed, we need to find a^b mod c.
Let d = a, after the operations d will become the answer.
Then, write out the binary expansion of b.
Then, for every bit to the right of the most significant bit, from left to right, do the following:
1. If that bit is a zero, square d, mod c.
2. If that bit is a one, square d, multiply that by a, mod c.
Let's see why that's true.
Out result was initially d = a = a^1.
Each time we squared d, we multiplied its power by 2 (if d at some point was a^k, then d^2 = (a^k)^2 = a^2k).
Each time we multiplied d by a, we added one to its exponent (if d = a^k then d*a = a^k * a = a^(k + 1)). We can reach any exponent we want by doing the binary expansion of it. In binary, squaring the number is the same by multiplying the exponent by 2, which in binary is a simple left shift. Multiplying by a is simply adding one to the power.
That's why we did every single bit to the right of the most significant bit, we were basically building the needed exponent in binary. Originally, it was 1 (d was = a = a^1), so the most significant bit is already accounted for.
Example:
3^11 mod 5
11 in binary - 1011.
d = a = a^1 = 3
Ignoring the most significant bit. The next one from left to right is a zero.
d^2 = 3^2 = 9
9 mod 5 = 4
d is now = 4
Notice that the power of a that d is is now 2, in binary it's 10, we've done a left shift of one bit.
The next bit is 1.
d^2 = 4^2 = 16
16 mod 5 = 1
d is now = 1
d*a = 1*3 = 3
3 mod 5 = 3
d is now = 3
The exponent of a in d in binary is now 5 (it was two, we multiplied it by 2 by squaring the number and added one by multiplying b by a) 5 in binary is 101.
The next (and the last) bit is 1.
3^2 = 9
9 mod 5 = 4
d is now = 4
4 * 3 = 12
12 mod 5 = 2
d is now = 2
Notice that the exponent now is eleven, just as we wanted, because its 5*2 + 1 = 11.
So, the result is 2. 3^11 mod 5 = 2.
This "square and multiply" algorithm is also very efficient, is requires n-1 steps (at the worst case n-1 square operations, n-1 multiplications by a and 2n-2 mods) where n is the amount of binary bits in the power/exponent you're trying to calculate (mathematically speaking, log2(exponent))
I hope you learnt something new today! :D
- After Watching this video
Asking my brain: Do you understood something?
Brain: I know this is a video so... Yep!
relatable lol
I feel proud of myself for being recommended these kind of videos even though I don’t understand shit
3:30 the essence of mathematical pursuit
but what would happen if you encrypt your second guess with the superposition of all the multipliers of p/2. Then you just substitute all the factors of the encrypred superposition multipliers in your other encrypted factors of p to get the same result, right?
*Core Insight*
It is very easy to calculate GCD of any 2 large unequal positive integers, and the result is always a factor of both, one of which being the composite number of your interest.
Given any factor of your composite numbers, there exist infinite multiples of this factor and you have to find only 1 of them to then use in GCD to get this unknown factor.
Through multiple attempts, Shor's algorithm mainly searches for any one of the many "other large positive integer" so that GCD can be used to get at least 1 factor of your composite number.
In each iteration, it generates a random positive integer "a" and computes the positive integer period "r" (using QFT for quantum speedup) such that if r is odd (bad luck) then retry with new "a" otherwise you got lucky in this iteration. Simply check if GCD > 1 and you got your non-trivial factor of the composite number of your interest.
My new goal is to comprehend this video. I project 100% comprehension by 2062.
Well, I think my brain just melted a little
Thank you so much..i had been losing sleep for so long so as to understand shors .Finally i got some gist of it :)
I think it's worth pointing out that the final quantum fourier transform doesn't just give a superposition of 1/p, 2/p, ...exactly. Instead, it gives a superposition of integers from say 0 to N-1 where N=2^n, n being the number of qubits representing the number (so N possible states). The states with the largest amplitudes are those integers closest to N/p, 2N/p, 3N/p, and so on. It is important to note that there are (possibly) non negligible probabilities that other nearby integers are measured instead, and that we need to divide this measurement by N to get a multiple of 1/p (or at least an approximate multiple of 1/p).
You can calculate the whole QFT yourself if desired, but you will find that the probability of measuring integer x is proportional to roughly sin^2(pi*f*ceil(1/f)*x)/sin^2(pi*f*x) with frequency f = p/N (and ceil is the ceiling function). This indeed has peaks around N/p, 2N/p, ... which can be seen by considering its envelope csc^2(pi*f*x) (also here I am ignoring the special case of x=0 which needs to be summed differently in the QFT)
Thanks, I was very confused on how you could get fractional number
One word
"Beautiful"
At 3:00, you say that you measure the same state |1/4347⟩ + |2/4347⟩ + ... multiple times to get several of the basis vectors so you can find their common factor. Then you have to prepare that state multiple times. But you got r = 71426 randomly at 1:39. Doesn't that mean that you have to force the state to collapse into r = 71426 all subsequent times? Is that what you do?
Within the conceptual framework depicted in the video, the point is that the actual value of r doesn't matter, in that the level sets of g^x will always be of the form {x,x+p,x+2p,...} and the p will be the same no matter which r you got. But in a real scenario where you have a finite (but sufficient) number of qubits, this isn't actually what happens, and instead you have some additional work to do to extract the period after that step. The Wikipedia article talks about the details.
3:11 What's that program?
It's been a year, did you figure it out? I want to know what program that is too. Looks fun.
I figured it out, its wolfram alpha mathematica. You're welcome
i had to watch this four and a half times in a row, but once i did, it all actually made sense.
If it was a vault of pies then I'm disappointed that you didn't use 314159 as the number instead
at 2:50, why can you measure more than one time, since it twill collapse?
I wish you did these videos back when I did my project on quantum computing 😭😭
Lol so many of your videos is just me watching and kind of paying attention and then getting to the end and going, huh?? And rewatching the video
I am currently trying to figure out a factoring method that a regular computer could use and recently discovered the Euclidean Algorithm by myself playing around with remainders.
When I go through a hard time with my thesis and think I am dumb and worthless, I look for videos like this to read the comment section. Seeing people saying that they don't understand makes me feel clever for a few minutes...
how to find the superposition of one number? like in 1:25 it says if we start with a superposition of all the numbers up to 314191, how do you find it? if there is a video explaining it, please tell me.
thank you
Me at the start of the video: hmm... sounds like a cool video
Me at the end of the video: Tf? Is he speaking English?
i undertood this video better than the other despite having watched the other one around 4 times!
so in order to find the common factor of a large number you must find the common factor of a large number - nice
Glad that he gave a recap..i mean im really glad
Did anyone forget we were trying to get pies by the end?
Great Explanation... just checked whether 829 and 379 are primes or not. They are primes
That's a great way to follow on the previous one. Thank you
I used more calories trying to understand this more than superficially than I would have received from eating the entire pie.
Your definition of small number is amazing
0:00 here from thumbnail hmm
1:00 OK that sounds interesting so far
2:00 duh let's go to comments section which would be more realistic😂
Thank you for this breakdown, very informative!
I was trained as a mathematician, and even I'll admit my eyes glazed over after the first minute.
oh extra thing which you could have used to not have to do another trial. 4347 may not be even, but it is divisible by 3. We know how to factorise x^3 - 1, so you could have checked common factors of x-1 and x^2+x+1 with 314191, where x = g^(p/3), and p/3 = 4347/3 = 1449, for g = 101. You would have found x-1 gives 829 and x^2+x+1 gives 379 as greatest common divisors.
Even in general, x-1 is always a factor of x^n - 1, so if we find n is a small divisor of p, we always have an easy one to check for common factors, namely g^(p/n) - 1.
Please can someone help?
(4 pts) A 30.0 kg child sits on one end of a long uniform beam having a mass of 20.0 kg, and a 40.0 kg child sits on the other end. The beam balances when a fulcrum is placed below the beam a distance 1.10 m from the 30.0 kg child. How long is the beam?
A)2.20 m B)1.98 m C)1.93 m D) 2.07 m E)2.12 m
"As a refresher, here's a rough overview of how Shor's algorithm factors large numbers quickly"
Me: "Ah shit, here we go again."
There are currently 42 comments, that's cool.
Great video, this answered my main question from the last video. It was a little undersatisfying because I didn't follow along on paper or with a calculator, but that's my fault not yours.
asailijhijr Casually solving 101^4347 with a pen and paper
I'm way too stupid for this channel idk why I'm still subscribed after a year or so
I like hw ur comment seems like ur seriously contemplating the question
Woah. That's a crazy complex way of getting factors. My question was why just finding the factors by going up the number line isn't faster, but then I realized that it's because the number in the video is MUCH shorter than the real encryption numbers.
The actual encryption numbers strength lie in the amount of time it takes to crunch the numbers because they are so long. This quantum algorithm is better because it crunches far fewer total calculations while being able to do most of the calculations it needs to at the same time instead of linearly. Regular computers couldn't do this calculation in a timely manner because they would be doing the quantum part linearly. So, a regular computer might crunch (for example, these are random stats for illustration) thousands of numbers millions of times running through the calculation traditionally, but a quantum computer would crunch simultaneous sets of thousands of numbers a few times. I think?
So what your saying is "in order to solve for P", MAGIC HAPPENS (T=3:56) Can you do a video on 'How to actually solve for P'; Also a brief explanation of how RSA uses co-primes would be awesome. Thanks I really do like your lectures
He did explain it. See 2:15 - 3:00.
I didn't know P has so much value. I used to flush it every time.
I still don't know my "times tables" from primary school by heart ... how do I understand these videos, and most importantly, why do I find this actually interesting.
2:03 wait, why do we need to put it in a QTF? Can't we just measure some values there and find p from them?
Kind of, yes, but also not exactly. Since we don't know x, and you'll get random results from the superposition, it's far from trivial to figure out p. It's much easier when you're only getting multiples of one specific number (1/p).
i don't understand a thing, yet i like physics, and i feel like i am learning even though i am not...
you are literally me.
@@erek Guess what, somehow I am now studying in UofT majoring in physics & astrophysics, kinda crazy.
@@wangamanga2128 that's cool. i'm the kind of person who can find possibly everything interesting as long as I can understand it
i haven't studied maths since high school. but I have a lot of hobby math yt channels that i watch.
i have majored in CS engineering (without maths)
i really do have a lot of respect for people who are in research. that I am being 100% honest. i plan to go for masters and PhD in future
Remember when this channel used to explain to us you should run when it's raining so you get less wet?
Bitwarden > Dashlane, especially if you care about security and quantum resistance.
"This is where we use me quantum computer..."
And this is where I got lost.
Another detail you glossed over: the Euclidean algorithm step you need to do in this problem is "anomalously cheap" compared to the size of the numbers because the big number is given as a known offset from a known power of a not-so-huge number. This means you can do modular exponentiation and thus keep your numbers from ever being any bigger than the square of the smaller of the given numbers. If this weren't the case and you had to actually work with, say, the binary expansion of 127^(8694)+1, then you would be better off just doing trial division by primes up to floor(sqrt(314191))=560.
So modular exponentiation is the key to calculating the GCD fast? I was already wondering about that. Using traditional Euclid's algorithm on 127^(8694)+1 and some other large number would take billions of years.
@@ericvosselmans5657 Yes. Following along with the video, the first Euclid algorithm step (which is the only one involving a number way bigger than the number you're trying to factor) is to get (127^8694 + 1) % 314191. The middle bit can be done using modular exponentiation by squaring; you record the remainders when dividing 127,127^2,127^4,127^8,...,127^8192 by 314191 and then multiply the ones that correspond to 1s in the binary expansion of 8694, so the exponents of 8192, 256, 128, 64, 32, 16, 4, and 2. Throughout that process you take remainders at each step, which keeps the numbers you're actually working with from getting any bigger than 314191^2.
Ok first of all, the -youtube- algorithm
Damn it lol
Can you really say that your sponsor is more secure than the bank vault when they in fact use non-quantum encryption?
I like how he said that the ad service would make you more secure than the vault with the pie, but.... it can't
luckily there's an easy way to check if you understood all this: grab two 3-digits primes, multiply them and try to factor the result with this method. If I had a lot of NRG I would surely do it
Hit me right in the brain in a good way! Thanks :)
Blink once and you're lost... I love it!
my brain just fell outta my nose 🧠👃
Well i understood it all so i can ascend now to the next dimension?