PARI's commands

[CRGreathouse]

Originally Posted by 3.14159

The former: A power check would be necessary, in order to avoid wasted time.

Do you want it to do trial division by small primes, some rho and SQUFOF, and a probable-prime test too, in case you forgot to do those? How about stopping ECM at some point and switching to a general-purpose factoring algorithm like SIQS?

Originally Posted by 3.14159

The latter: Please show me a link which shows the factors of RSA1024.

So just because no one has made the factors of a particular composite public, you feel safe assuming no one can find the factors?

And of course when you're using an RSA key you're looking to keep it secret in the future, not the past.

But hey, maybe your security just isn't valuable enough to protect.

[3.14159]

sigma(71608085354600097239391307^4) took an hour to factor via SIQS. The disappointing part is, that the cofactor's factors were a p7, p18, and p77. It's a surprise that ECM missed a p7 and a p18.

[CRGreathouse]

Originally Posted by 3.14159

sigma(71608085354600097239391307^4) took an hour to factor via SIQS. The disappointing part is, that the cofactor's factors were a p7, p18, and p77. It's a surprise that ECM missed a p7 and a p18.

Pari took 2.15 seconds on my machine to factor that number.

[Mini-Geek]

Originally Posted by 3.14159

sigma(71608085354600097239391307^4) took an hour to factor via SIQS. The disappointing part is, that the cofactor's factors were a p7, p18, and p77. It's a surprise that ECM missed a p7 and a p18.

You'd have to do a very VERY small amount of ECM, or be impossibly unlucky, to miss a p7 and p18. I think most likely, this number was never ECM'd.

[3.14159]

For me, it was the latter, for YAFU's ECM. PARI's ECM factored it with ease.

And, about QS; How does the comp determine the amount of relations that are necessary to factor a number?

An example would be the number 2802104782336128351749706435932730996816588058828391669. SIQS reports the following, "2312 relations needed".

I've recently taken on learning something about how it works. I know the very basic stuff about it, but not much else.

[Mini-Geek]

Originally Posted by 3.14159

For me, it was the latter, for YAFU's ECM. PARI's ECM factored it with ease.

AFAIK, YAFU doesn't ECM at all before running SIQS if you tell it to run with the siqs() command. If you use the factor() command, then it runs ECM and should've found the factors.

[3.14159]

Originally Posted by Mini-Geek

AFAIK, YAFU doesn't ECM at all before running SIQS if you tell it to run with the siqs() command. If you use the factor() command, then it runs ECM and should've found the factors.

Indeed. siqs(n) goes directly to the quadratic sieve. In factor(n), SIQS is pretty much the "last resort" method, should trial division, Fermat's, Rho, P+1(?), and ECM all fail to factor the number completely. Though, it's still puzzling that it missed a p7 and a p18. I would have expected it to at least be present as a composite, the product of the p7 and p18.

(?) = "Does it use P+1"?

[bsquared]

Originally Posted by 3.14159

Indeed. siqs(n) goes directly to the quadratic sieve. In factor(n), SIQS is pretty much the "last resort" method, should trial division, Fermat's, Rho, P+1(?), and ECM all fail to factor the number completely. Though, it's still puzzling that it missed a p7 and a p18. I would have expected it to at least be present as a composite, the product of the p7 and p18.

I'm not sure what you were expecting if you just ran SIQS. The only thing SIQS does prior to sieving is check for small factors (it does trial division up to 10k, IIRC) and perfect squares. After that, it will not find any factors until sieving, linalg, and sqrt are complete.

Originally Posted by 3.14159

(?) = "Does it use P+1"?

yes, factor() uses P+1 with three different random bases. default B1= 20,000.

[bsquared]

Originally Posted by CRGreathouse

Pari took 2.15 seconds on my machine to factor that number.

I know this is the pari/gp thread, but here's a gratuitous yafu plug:

11/21/10 20:31:08 v1.20 @ AVA-343686, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.0.1
detected AMD Phenom(tm) II X4 955 Processor
detected L1 = 65536 bytes, L2 = 6291456 bytes, CL = 64 bytes
measured cpu frequency ~= 3209.987220

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78504 primes. pmax = 1000099


>> factoring 262934907404708576862758446841091336882604808443805210895581843776020374194863215112535
94913093697297001

div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 1, starting 1000 iterations on C102
rho: x^2 + 3, starting 1000 iterations on C102
rho: x^2 + 2, starting 1000 iterations on C102
pp1: starting B1 = 20K, B2 = 1M on C102
pm1: starting B1 = 100K, B2 = 5M on C95
Total factoring time = 0.3290 seconds


***factors found***

P3 = 211
PRP7 = 2487811
PRP18 = 887712475607927971
PRP77 = 56425586867064181439411544449942718884745465011098050341509361224221109755611

looks like rho found the p7, and P-1 found the P18.

[bsquared]

errr, sorry. P+1 found the p7.

ran out of edit time...

[3.14159]

Originally Posted by bsquared

errr, sorry. P+1 found the p7.

ran out of edit time...

... Isn't editing time one hour? It;s only been 23 minutes since you made the post.

I noted the source of the problem. Another difference between 32/64 bit programs.