Giter VIP home page Giter VIP logo

Comments (1)

Hermann-SW avatar Hermann-SW commented on June 7, 2024

I found this online calculator doing superfast gaussian factoring:
https://www.alpertron.com.ar/GAUSSIAN.HTM?

It factors 2082-digit prime in 3 seconds!
And composite number RSA-59 in few seconds (composite numbers are harder).

The corresponding repo is here:
https://github.com/alpertron/calculators

"make gaussian" builds the executable.
Here factorization of 120-digit first RSA-240 prime factor:

$ time ./gaussian 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 1
2<p>Factors of 509435 952285 839914 555051 023580 843714 132648 382024 111473 186660 296521 821206 469746 700620 316443 478873 837606 252372 049619 334517 (120 digits) + 0 i<ul><li>664725 951658 524848 356077 798734 408273 267435 380913 396313 107174 (60 digits) + 259952 613907 820517 149425 140676 632621 008474 102347 669603 089079 (60 digits) i</li><li>664725 951658 524848 356077 798734 408273 267435 380913 396313 107174 (60 digits) - 259952 613907 820517 149425 140676 632621 008474 102347 669603 089079 (60 digits) i</li></ul><p>Time elapsed: </p><p>Written by Dario Alpern. Last updated on 4 December 2022.</p>

real	0m0.014s
user	0m0.011s
sys	0m0.003s
$

I did fork that repo and made its output more Python friendly:
https://github.com/Hermann-SW/square_sum_prod

$ ./square_sum_prod 1105 py; echo
2,1,3,2,4,1
$

[ 1105 = 5*13*17 = (2²+1²)*(3²+2²)*(4²+1²) ]

And used in my RSA_numbers_factored.py Gist:
https://gist.github.com/Hermann-SW/839dfe6002810d404e3f0fe1808a6333

$ python -q
>>> from RSA_numbers_factored import RSA, square_sums
>>> R = RSA()
>>> R.square_sum_prod(1105)
[2, 1, 3, 2, 4, 1]
>>> square_sums(R.square_sum_prod(1105))
[[4, 33], [9, 32], [12, 31], [23, 24]]
>>> square_sums(R.square_sum_prod(1105), revt=True, revl=True)
[[33, 4], [32, 9], [31, 12], [24, 23]]
>>> 
>>> l,n,p,q = R.get(240)
>>> R.square_sum_prod(p)
[664725951658524848356077798734408273267435380913396313107174, 259952613907820517149425140676632621008474102347669603089079]
>>> 

For sum of square I ignored conjugant factors, but you could use all factors determined.
You might fork Alpertron's repo and make it produce the complete guassint output for use in Python.
And use my subprocess.Popen() method of just calling out to that superfast C implementation.

P.S:
My above work is 3 years ahead of time, I will become student of mathematics (number theory) at age of 60 in 2025 ...
https://twitter.com/HermannSW/status/1586024568434692097

from number-theory-python.

Related Issues (2)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.