RSA_numbers_factored_mp.py

[Hermann-SW]

I started project wrt RSA numbers in Python:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/python/RSA_numbers_factored.py

Later I added type hints and generated documentation with lazydocs:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/python/docs/RSA_numbers_factored.py.md

I transpiled manually to JavaScript for use in NodeJS and in the browser:
https://github.com/Hermann-SW/RSA_numbers_factored#functionality-validation-python-browser-and-nodejs-demos

Yesterday I aseked myself whether playing with up to 2048-biit RSA numbers is possible in MicroPython, and it is!
I had to get rid of sympy, itertools and typing libraries, but the rest just worked in minicom session on my RP2040:

$ minicom -D /dev/ttyACM0


Welcome to minicom 2.8

OPTIONS: I18n 
Port /dev/ttyACM0

Press CTRL-A Z for help on special keys

>>> from RSA_numbers_factored_mp import RSA
>>> RSA = RSA()
>>> for r in RSA.factored((1,1)):                                               
...     l,n,p,q = r[0:4]                                                        
...     print(l)                                                                
...     assert n == p*q                                                         
...     for a,b in RSA.square_sums(r):                                          
...         assert n == a**2 + b**2                                             
...                                                                             
...                                                                             
...                                                                             
59                                                                              
129                                                                             
180                                                                             
230                                                                             
768                                                                             
>>> RSA.square_sums(59)                                                         
[[38768728061109707828243001823, 264836754409721537369435955610], [938612054137...
>>> RSA.get(59)[0:2]                                                            
[59, 71641520761751435455133616475667090434063332228247871795429]               
>>> 

If you are not intereested in RSA numbers, you might just want to use the simplified "isprime()" function I implemented. For numbers less than 2^81 it is definitive!

You can verifiy the number of primes up to 100000 here:
https://primes.utm.edu/howmany.html

Welcome to minicom 2.8

OPTIONS: I18n 
Port /dev/ttyACM0, 22:14:00

Press CTRL-A Z for help on special keys


>>> from machine import reset                                                   
>>> reset()                                                                     
                                                                                
>>> from RSA_numbers_factored_mp import isprime                                 
>>> len([p for p in range(100000) if isprime(p)])                               
9592                                                                            
>>> len([p for p in range(10000) if isprime(p)])                                
1229                                                                            
>>> len([p for p in range(1000) if isprime(p)])                                 
168                                                                             
>>> len([p for p in range(100) if isprime(p)])                                  
25                                                                              
>>> len([p for p in range(10) if isprime(p)])                                   
4                                                                               
>>> 

You can find the MicroPython version here:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/python/RSA_numbers_factored_mp.py
I uploaded it to RP2040 with ampy and then used it as shown above.

P.S:
You might ask why one should do several 100 digit arbitrary precision number arithmetic in MicroPython.
My answer would be: because you can ;-)

[Hermann-SW]

There was a problem with MicroPython implemented "gcd()" because sympy is missing in MicroPython.
Recursive implementation was no problem for Python, but ran out of stack space for MicroPython.
New commit makes "gcd()" non-recursive:
Hermann-SW/RSA_numbers_factored@df06536

Now RSA_numbers_factored validation demo runs on MicroPython as well — but it takes 3:09min instead of 1 second in Python or even in browser JavaScript. Anyway it works:

>>>                                                     
MPY: soft reboot                                        
MicroPython v1.19.1-900-gfc4c47f7b on 2023-02-27; Raspberry Pi Pico with RP2040
Type "help()" for more information.
>>> from RSA_numbers_factored_mp import RSA
>>> RSA = RSA()
>>> RSA.validate()

with p-1 and q-1 factorizations (n=p*q): 20
 59 digits, 79 digits,100 digits,110 digits,120 digits,129 digits,130 digits,
140 digits,150 digits,155 digits,160 digits,170 digits,576 bits  ,180 digits,
190 digits,640 bits  ,200 digits,210 digits,704 bits  ,220 digits,
                                                                                
without (p-1) and (q-1) factorizations, but p and q: 5                          
230 digits,232 digits,768 bits  ,240 digits,250 digits,                         
                                                                                
have not been factored sofar: 31                                                
260 digits,270 digits,896 bits  ,280 digits,290 digits,300 digits,309 digits,   
1024 bits  ,310 digits,320 digits,330 digits,340 digits,350 digits,360 digits,  
370 digits,380 digits,390 digits,400 digits,410 digits,420 digits,430 digits,   
440 digits,450 digits,460 digits,1536 bits  ,470 digits,480 digits,490 digits,  
500 digits,617 digits,2048 bits  (=617 digits)                                  
                                                                                
>>>

[rkompass]

This is nice and impressing.
Could you give some links to the mathematical backgrounds and your motivation in the beginning?
Did your project start with reading the stackexchange question ?

[Hermann-SW]

This is nice and impressing. Could you give some links to the mathematical backgrounds and your motivation in the beginning?

It started with RSA numbers, and challenges of factoring a big number known to be product of two odd primes. There were many prices that were earned.
I am interested because I want to challenge the "s" in https in efficiently factoring big numbers, will become a student of mathematics (number theory) end of 2025 at age of 60 after early retirment:
https://twitter.com/HermannSW/status/1586024568434692097

The big functionality validation (snapshot) shows all the mathematical identities possible with the lib sofar:
https://github.com/Hermann-SW/RSA_numbers_factored#functionality-validation-snapshot

I started with number theory identity "pow(a, p-1, p) == 1" for prime p, and added what I found elsewhere. The lib (not the MicroPython version) should allow to quickly test theories and ideas as well as make calculations.

I was able to factor 100-digit number RSA-100 in 2.5 hours on my laptop (in 24h on Raspberry Pi400) with msieve.
There is way to go for factoring 617-digit (2048-bit) number RSA-2048 (if that is possible at all).

Did your project start with reading the stackexchange question ?

I found that posting on my long search for efficient algorithm to compute the unique squares that sum up to a prime of the form 4*k+1. For RSA numbers there are exactly two such sum of squares.

I tried to contact Robert Chapman (the author of the stackexchange posting), but then found out that he died unexpectedly in 2020:
https://forums.raspberrypi.com/viewtopic.php?p=2057616#p2062076

I derived fomulas for ".square_diffs()" function here:
https://github.com/Hermann-SW/Mathematical-expressions/blob/main/Number%20theory/Odd%20prime%20iff%20unique%20difference%20of%202%20squares.md

It is just nice to easily play with RSA numbers, here RSA-129, the very first RSA challenge from 1977, factored 1994 with 100$ reward:

pi@pi400-64:~/RSA_numbers_factored/python $ python -q
>>> from RSA_numbers_factored import RSA, digits, bits
>>> RSA = RSA()
>>> l,n,p,q = RSA.get(129)[0:4]
>>> digits(n)
129
>>> l
129
>>> n == p*q
True
>>> RSA.square_diffs(129)
[[18129831252057180249554918905369179773297703803243165191894554555, 14639301741209529300407069285465281639879939164749777347903733978], [57190812878944433834617889988073306005109148360621181281280921467853467622866948915298561781979352529494537573799645013439771771, 57190812878944433834617889988073306005109148360621181281280921467853467622866948915298561781979352529494537573799645013439771770]]
>>> for a,b in RSA.square_diffs(129):
...     n == a**2 - b**2
... 
True
True
>>> 

Python lib documentation:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/python/docs/RSA_numbers_factored.py.md

[rkompass]

So, did you find a combination of routines that are better than quadratic sieve and its variations? Or simpler to implement? Or use much less memory (the quadratic sieve seems to need much memory for storage)?

[Hermann-SW]

So, did you find a combination of routines that are better than quadratic sieve and its variations? Or simpler to implement? Or use much less memory (the quadratic sieve seems to need much memory for storage)?

General number field sieve is better than quadratic sieve.
In thread Pi400 factoring 100-digit number overclocked (2.2GHz) in ̶1̶2̶.̶8̶H̶ 12.1h I used a fork of msieve to allow to do exactly the same computations on different CPUs and compare performance:
https://github.com/Hermann-SW/msieve#readme
It turned out that (sequential) msieve performance correlates with single core performance of CPUs.
But msieve allows to greatly parallelize one stage of the 3(4) stages of computation — I will have to learn how to do that (because I have access to a workstation with 48 cores).
I expect to be able to make real progress only after having learned everything of number theory and its prerequesites when studying mathematics at University of Heidelberg/Germany end of 2025 ...

But I will keep RSA_numbers_factored.py growing over time, before 2025 and after.