Featured request

[xilman]

Originally Posted by bsquared

There are certainly algorithms that can prove primalty of such small numbers very quickly, I just haven't implemented any of them (I'm thinking in particular of APRCL). Pretty much all of the time I'm ok with the 1 chance in 4^20 that the PRP's have of actually being composite. If there ever comes a day when I just have to know for sure, I'll go to somewhere like WolframAlpha or Alpertron's webpage :)

Anyone have an APRCL implemention they would want to contribute to YAFU?

FWIW, my update Perl script for the GCW tables runs

return `echo "${big_mem}isprime($num,2)" | /usr/bin/gp -f -q ` == 1;

I'm sure you could adapt it to your situation.

[bsquared]

Originally Posted by Dubslow

As a newcomer only just stretching his sights beyond GIMPS, I had lots of fun using it.

Glad to hear it, let us know if you have any other questions.

[bsquared]

Originally Posted by xilman

FWIW, my update Perl script for the GCW tables runs

return `echo "${big_mem}isprime($num,2)" | /usr/bin/gp -f -q ` == 1;

I'm sure you could adapt it to your situation.

That's great, as long as the user has gp installed on their system. I don't want to require that.

@ CRG, my license (public domain) is not compatible with GPL, so it looks like PARI's implementation is out of bounds.

Thanks for the suggestions.

[Dubslow]

Originally Posted by Dubslow

it's clear that FactorDB does use an actual primality test, and it's able to run those on 80+ digit numbers in less than a second

http://factordb.com/status.php

It reports one core of a 2600 "Proving probable primes <300 digits". I guess it's as simple as asking in the FDB forum what that core runs?

[bsquared]

Originally Posted by Dubslow

http://factordb.com/status.php

It reports one core of a 2600 "Proving probable primes <300 digits". I guess it's as simple as asking in the FDB forum what that core runs?

I believe it uses primo but it could also be pari.

[Dubslow]

If I don't start YAFU in the dir which contains it, then it can't find yafu.ini or ggnfs binaries. Is there an easy fix for this? (Preferably yafu would always be able to find these things without having to pass in a cmdline switch.)

[Mathew]

Dubslow,

On *NIX systems I copied the yafu binary and the .ini file in /usr/local/bin.
This allows one to just type:

yafu "factor(<number>)"

Which works until the ggnfs stage.

For some reason yafu ignores the ggnfs line in the .ini file, but it reads the ecm line perfectly.

[bsquared]

I think there is a simple way to make everything relative to the binary location. I'll look into that.

[Dubslow]

Regarding the PRP->P thing, what about whatever aliqueit uses? It certainly sees more than enough numbers going through that the PRP error rate is significant, so it has to have some primality proving algorithm in it.
(The closest thing I could find to a license was this:

You may use the source and program however you see fit. I accept no 
responsibility for anything untoward that may happen to you, though I have no 
reason to suspect any such thing should happen. In the land of the free they 
are happy to try and sue you for anything though. You may not use this program 
unless you accept this agreement and take responsibility for your own actions. 
Otherwise, no soup for you!

)

[bsquared]

Originally Posted by Dubslow

... It certainly sees more than enough numbers going through that the PRP error rate is significant, ...

It does not have a prime proving algorithm in it - it uses the GMP function mpz_is_probab_prime_p with 25 witnesses, similar to what YAFU already uses. The chance of a composite being identified as prime is upper bounded by 4^-25 with this approach, so unless aliqueit has tested several times more than 1e15 numbers, the error rate is still essentially nil.

By default, YAFU uses 20 witnesses in mpz_is_probab_prime_p, or 1 chance in a trillion of being wrong on a random input.

[xilman]

Originally Posted by bsquared

By default, YAFU uses 20 witnesses in mpz_is_probab_prime_p, or 1 chance in a trillion of being wrong on a random input.

The true error rate is actually very much smaller than that.

The maximum error rate of a Miller-Rabin PRP is 1/4. The maximum is only achieved for a small subset of the composites; for most the rate is much much smaller.