I want to know how to factor this number only given $n$ and $e$, I have tried to factorize $n$ using Fermat's little theorem and also tried primefac module in python (running for the past 4 days) but had no luck, and I want to know how $n$ can be factorized.
For the values follow this link: https://pastebin.com/37WFzBvm
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Your best bet is running the General Number Field sieve (implemented by e.g. CADO-NFS or msieve) on a bunch of beefy computers. The GNFS is the only algorithm to have ever been used to factor 512-bit integers and in fact there is an open-source script (collection) Factoring-as-a-Service that will automatically factor a given number using AWS EC2 for about 100USD (in 2015, now it can probably be adjusted to use newer, faster instances which are cheaper).
Of course using the GNFS should always stay the last resort option. What you have tried so far (without luck it seems):
- An optimized variant of Pollard-Rho, which finds small factors quite fast.
- An optimized variant of the quadratic sieve (single-threaded), which brute-force-factors numbers up to about 250-300 bit faster than the GNFS.
- Pollard p-1 and William's p+1 factoring which work quite well if either of p-1 or p+1 has a smooth factorization
- The Elliptic Curve Method (ECM) which should find small factors up to about 200 bit (larger if more time).
What I could still imagine to maybe work is some Fermat-Factoring or maybe the Special Number field sieve.
But then, the proper strategy probably depends on the context in which you encountered this. If it was during e.g. a security review and you want to demonstrate the insecurity, then the GNFS is probably the way to go, if you encountered this during some homework, then some algorithm you learned prior is probably the way to go.
-
$\begingroup$ I no longer have access to a computer and I m broke. What solutions to do it on Android? $\endgroup$ Commented Aug 13 at 13:24