Several people claim to have found an efficient algorithm to factor
large integers. If you want me to look at your algorithm, please first factor
one of the numbers below.
These small challenges are hard enough so that
naive algorithms will not be able to solve them, and easy enough so that
an implementation on a personal computer should be able to solve them
(if the corresponding algorithm is really efficient).
Contrary to what was the case for the
official RSA
challenge, there is no money to win here!
rsa-59 = 71641520761751435455133616475667090434063332228247871795429 (59 digits, factors p=200...437 and q=357...017 have both 30 digits)
rsa-79 = 7293469445285646172092483905177589838606665884410340391954917800303813280275279 (79 digits, factors p=848...977 and q=859...727 have respectively 39
and 40 digits)
rsa-99 = 256724393281137036243618548169692747168133997830674574560564321074494892576105743931776484232708881 (99 digits, factors p=486...193 and
q=527...217 have respectively 49 and 50 digits)
rsa-119 = 55519750778717908277109380212290093527311630068956900635648324635249028602517209502369255464843035183207399415841257091 (119 digits, factors p=106...387 and q=520...393 have both 60 digits)
Once you have solved the above challenges,
to really convince me you have found an efficient factoring algorithm,
please do the following:
- pick up a large unfactored publicly known integer, say N
(RSA-1024
should be enough to convince me and many other people);
- from the factorization N=pq you have, deduce the private key
d = 1/e mod (p-1)(q-1) corresponding to the public key
e=65537;
- compute c = 3d mod N;
- send the integer c to me (or publish it on some web page);
- on my side, I will compute m = c65537 mod N and check
that m=3.
This algorithm is secure for both you and me:
- you cannot cheat since for that you need to extract an e-th root
of N; this is known as the
RSA problem;
- I cannot deduce the factorization of N from the value of
c.
Thanks to my colleagues Guillaume Hanrot,
Pierrick Gaudry and Emmanuel Thomé, who helped me improving this page.