RSA Factoring Challenge

The RSA Factoring Challenge is a set of factorisation challenges that involve numbers with hundreds of digits. The highest one cracked was RSA-250, which was 250 digits long, 829 bits, and was factored in February 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann (what’s with the cool names?). The number was:

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

The factorisation was:

6413528947707158027879019017057738908482501474294344720811685963202453234463 0238623598752668347708737661925585694639798853367 × 3337202759497815655622601060535511422794076034476755466678452098702384172921 0037080257448673296881877565718986258036932062711

According to Wikipedia, the factorisation process utilised approximately 2700 CPU core-years, using a 2.1Ghz Intel Xeon Gold 6130 CPU as a reference. The program used to factorise RSA-250 was the Number Field Sieve algorithm, using the open source CADO-NFS software.

The dedication of the factorisation was towards Peter Montgomery, an American mathematician known for his contributions toward computational number theory and cryptography. He passed away on February 18, 2020.

The highest unsolved RSA Factoring Challenge is RSA-2048, with a whopping 617-digit number (2048 bits), with the number being:

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

And if the factorisation was found, the prize would have been US$200,000 but the challenge ended before anyone was awarded the prize. RSA-2048 may not be factorable, unless in the future, considerable advances in integer factorisation or computational power are made.

There are many other challenges, like RSA-617 with 617 digits, which still has not been factored, and the smallest RSA challenge number is RSA-260, which is:

22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

So, if RSA-260 is cracked, I will be posting about it.

I think tomorrow, I’ll do the Riemann Hypothesis if I have enough time.

One thought on “RSA Factoring Challenge

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.