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.