Java programm that factors a number N=p*q into p and q using the period finding approach.
Java
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
primenumberdecomposer
README.md

README.md

This is a Java program, that decomposes a number N into two prime numbers p and q using a classical variant of Shor's algorithm (period finding approach).

Performance

Now it is working deterministically (checking all a's) and takes for a 31 bit N around 15 minutes on my 4x2.00GHz processor. For smaller numbers, the runtime decreases drastically!
If you want to make it faster, you can cheat (at least in the language of Quantum Computers) and set maxPeriode=2;

How to run

Download and compile with javac. Precompiled jar's might be added later.

TODO

  • Make p=q; N=p^2 work!
  • Use BigInteger for p, q and N (so that we can factor larger N's than 32bit!)
  • Allow inputs
  • Set conditions for failing cases (N can not be factorized in only two prime factors)
  • Better Documentation
  • Make a nice UI

change log

21.10.2016 - inital release
This is the intial working version. Not thoroughly tested yet.