Implement Shor's factorization algorithm #1070
Conversation
* Fix GetEuclidGCD
Implement the actual Euclidean Algorithm
* Replace == with ===
* Lua > JS
* Standard sucks
* Oops
* Update GetEuclidGCD.js
* Updated Documentation in README.md
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
| */ | ||
| function isValidP (A, B, p) { | ||
| // A^p = mB + 1 => A^p - 1 = 0 (mod B) | ||
| return (A ** p - 1n) % B === 0n |
There was a problem hiding this comment.
A ** p may grow rather large (thus being inefficient to compute). Couldn't you rewrite this using integer exponentiation and applying % B after every operation (modular arithmetics!), then subtracting 1n at the end, and finally taking that mod B again?
There was a problem hiding this comment.
Instead of subtracting, I can just check if it is 1 (mod B).
|
Any suggestions? |
See my review comment above: Leverage modular arithmetics to keep your numbers small. Example from my Lua implementation of the Miller-Rabin primality test. |
That could be an interesting idea. But my worry is that is could make the algorithm slower, i will check though. |
Implemented the classical version of Shor's quantum algorithm for factorizing integers.