How Shor's Algorithm Factors 314191
Вставка
- Опубліковано 21 тра 2019
- Go to www.dashlane.com/minutephysics to download Dashlane for free, and use offer code minutephysics for 10% off Dashlane Premium!
Watch the main video: • How Quantum Computers ...
Support MinutePhysics on Patreon! / minutephysics
This video explains how Shor’s Algorithm factors the pseudoprime number 314191 into its prime factors using a quantum computer. The quantum computation relies on the number-theoretic analysis of the factoring problem via modular arithmetic mod N (where N is the number to be factored), and finding the order or period of a random coprime number mod N. The exponential speedup comes in part from the use of the quantum fast fourier transform which achieves interference among frequencies that are not related to the period (period-finding is the goal of the QFT FFT).
REFERENCES
RSA Numbers (sample large numbers to try factoring)
en.wikipedia.org/wiki/RSA_num...
IBM on RSA www.ibm.com/support/knowledge...
Modulo Multiplication Group Tables mathworld.wolfram.com/ModuloMu...
Difference of squares factorization en.wikipedia.org/wiki/Differe...
Euclid’s Algorithm en.wikipedia.org/wiki/Euclide...
Rational sieve for factoring en.wikipedia.org/wiki/Rationa...
General Number field Sieve en.wikipedia.org/wiki/General...
Scott Aaronson blog post about Shor’s Algorithm www.scottaaronson.com/blog/?p...
Experimental implementation of Shor’s Algorithm (factoring 15, 21, and 35) arxiv.org/pdf/1903.00768.pdf
Adiabatic Quantum Computation factoring the number 291311 arxiv.org/pdf/1706.08061.pdf
Scott Aaronson course notes www.scottaaronson.com/qclec/ www.scottaaronson.com/qclec/c...
Shor’s Algorithm on Quantiki www.quantiki.org/wiki/shors-f...
TLS And SSL use RSA encryption en.wikipedia.org/wiki/Transpo...
Dashlane security whitepaper www.dashlane.com/download/Das...
Link to Patreon Supporters: www.minutephysics.com/supporters/
MinutePhysics is on twitter - @minutephysics
And facebook - / minutephysics
Minute Physics provides an energetic and entertaining view of old and new problems in physics -- all in a minute! Created by Henry Reich - Наука та технологія
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
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
I understand some of these words
there is a hair on the camera you took the photo of you with
@@marc_frank I understand some of these words...
@@GetawayFilms yea
This example makes the original video make much more sense! Thanks!
Yes, I was wondering how the hell the QFT worked!
@@baileyridley8344 ikr
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!
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!
This is a really great follow up to the previous video. Really helps to illustrate just how powerful this algorithm is.
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.
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.
Found the video really helpful! I would highly recommend watching this for starters before formally learning Shor's algorithm in class.
Great video, directly answered all the questions I had from last video :)
Great work. One of the best explanations I have seen.
This was so complex but you made me understand it so you did a good job
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?
Amazingly concise and lucid explanation.
Thank you for this breakdown, very informative!
Nice follow up to the previous video. Much clearer now.
I don't understand your videos for most of their part but I just like to watch them. They are like poems of numbers.
Really outstanding explanation and presentation!
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.
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
That's a great way to follow on the previous one. Thank you
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
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
4:36 I can have my pie, but can I eat it too?
Answer: yes, because of superposition
Thank you so much..i had been losing sleep for so long so as to understand shors .Finally i got some gist of it :)
You want a video with 100M views? Do one about UA-cam's algorithm. LOL
I wish you did these videos back when I did my project on quantum computing 😭😭
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.
3:30 the essence of mathematical pursuit
*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.
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.
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
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
Glad that he gave a recap..i mean im really glad
Thanks Henry!
Good Job. Had to watch it two times, but now it´s crytal clear how a period is calculated for RSA. For the log-problem it´s kinda easy to see where the period comes from... The common example for periods of vortices in multidimensional cubes really hindered my enlightment. Thank ya
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
Hit me right in the brain in a good way! Thanks :)
This is one of those videos that feel ten times as long as it actually is
i undertood this video better than the other despite having watched the other one around 4 times!
i had to watch this four and a half times in a row, but once i did, it all actually made sense.
Your definition of small number is amazing
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.
minutephysics now has become into minutecomputations
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?
cool vidéo thank you, i just don't understand how you perform your calculation. how were you able to get results when you would have needed a superpostion of pi*100 states?
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?
going back to the Addition channel and working my way up to this.
Play it at 0.75X it will be way more understandable and easy to follow him
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
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.
One word
"Beautiful"
These videos were the best you ever created
Loved this!
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
I love this channel it is amazing
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
This is truly amazing :O
So is there any guarantuee to find a working solution faster than O(n)? Otherwise there can be situations where the intermediate results are always not divisible by 2 until you've made n guesses.
Don't think I didn't notice you referencing Vi Hart's 2019 Pi video
Great Explanation... just checked whether 829 and 379 are primes or not. They are primes
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.
Well, I think my brain just melted a little
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.
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
This is amazing
minutephysics: shor's algorithm
me: haha numbers go brrrr
minutephysics: *pie*
me: PIE
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
Oh ok, thanks for clearing that up.
The wikipedia link for the Euclid’s Algorithm is not correct, I think is missing a %20 (space). Is wolfram alpha what you are using to calculate (101^4347-1)/3141591 ?
Thanks!
Please make a video on Quadratic Sieve Algorithm with an example. Please...
1 minute in, and I'm already asking myself why the computer can make golf ball waffles
What is the music in the background? Thanks!
- After Watching this video
Asking my brain: Do you understood something?
Brain: I know this is a video so... Yep!
relatable lol
Is there a way to avoid the odd number problem? Or at least reliably generate a guess that will work if the first guess won't?
It's probabilistic. The chance that you'll get an even power and a nontrivial factor is at least 37.5% for a random guess.
I was trained as a mathematician, and even I'll admit my eyes glazed over after the first minute.
If you take 2 blocks, one is stationary near an indestructible wall, and the other has a mass of 10 to the X kilograms, assuming there is no friction, the amount of collision will compute pi.
3Blue1Brown made a video on this and explains it better, watch it because it gets very satisfying later.
Can anyone explain how qbits can be used to generate a superposition of numbers?
Can you make a video about QFT?
OK, so I have written some sort of implementation but my issue comes from computing gcd(g^p - 1, N) and gcd(g^p + 1, N). Basically, g to the power p gives me an overflow error. Is there a way around this? A way where I don't need to use Big Integer values which take hundreds of bits to store. Some memory efficient trick like modular exponentiation.
Okay, to get the gcd of two large numbers p, q, you just need the remainder of the larger one, say p, mod the smaller number, say, q. Since that remainder is always smaller than q, we swap their order. So, gcd(p, q) = gcd(q, p mod q). That can be done recursively until any number becomes zero, then we return the other one.
Therefore, we don't need to store the whole number g^p ± 1 to get the gcd. At any step we need just the mod N part of it.
So you don't need to compute g^p ± 1, you need to compute g^p ± 1 mod N. You can use any modular exponentiation algorithm for that. If you're using Java then I'd stick with the BigInteger.modPow(BigInteger power, BigInteger modulus) method. I think its a variant of the so called square and multiply algorithm.
I didn't know P has so much value. I used to flush it every time.
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
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😂
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.
Im a bit confused at the Quantum fourier transform stage, once you have a superposition of 1/p, 2/p, 3/p and so on, how is 1/p the common factor? And how after you find that 1/p is the common factor do you calculate p?
If 1/p is the common factor then p = 1/(1/p) with basic algebra. If you have a superpositition of 1/p, 2/p, 3/p, you could run the algorithm several times to get different results, say, 2/p, 17/p, 4/p, 5/p. Every once in a while you're guaranteed to get a result n/p such that n is coprime to p because p has finitely many prime factors. Amassing several n1/p, n2/p, n3/p... all being coprime to p will make you really confident that 1/p is the common factor, because the fractions are irreducible and have the biggest denominator out of all others. You'll just discard everything else that resulted in a reduced fraction that would give an incorrect but necessary smaller value of p (n is always bigger than or equal to 1). You can always check which are correct in the case when you're uncertain, though.
There is someone I know of who has allegedly created a quantum computer simulator, which runs in approximately similar computer time to the theoretical quantum time. Not sure how much of that is accurate, but if it is...
She was dragging her feet about working with the professor on this project, and was going to sign over rights to either him or some corporation. My colleagues and I referred her to good patent attorneys.
Shouldn't the qft resulting state collapse once we measure it?
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
Blink once and you're lost... I love it!
This just totally blew mind, it's so unbelievable to me that quantum computers can just totally ignore any laws of NP-hard problems
Please correct me if my questions are flawed due to my own misunderstanding, but is the strength of quantum computing just that it's massively, massively parallel? Is that parallelism allowing it to do (relatively) simple checks on all of the results of a "bad" guess at once? Could Shor's Algorithm just be applied on an absurdly large cluster of very weak processors in a reasonably effective way? Has the NSA already bought a couple gazillion Zilog Z80s to break all of our encryption?
The answer to your first question is basically yes, but the answer to your followup questions is basically no. The reason for the gap is kinda obvious when you actually see how the intermediate results of an example go (which is the beautiful thing about this video). The classical way to do the period finding step that Shor's algorithm uses is to just compute g^x mod N for a whole bunch of x's until you get a value you got before. Intuitively the problem is that the period you're looking for is likely way bigger than N (like we saw in the video where factoring a 6 digit number ended up with a period with >17000 digits), so the "classical Shor's algorithm" is ostensibly worse than trial division. That intuition is a little bit misleading but nonetheless the discrete logarithm (which is what is asked for in this period finding step) is about equally as hard as factoring, classically speaking.
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
I feel proud of myself for being recommended these kind of videos even though I don’t understand shit