mersenneforum.org > YAFU Featured request
 Register FAQ Search Today's Posts Mark Forums Read

2012-03-28, 17:29   #23
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

101101110100012 Posts

Quote:
 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
Code:
return echo "${big_mem}isprime($num,2)" | /usr/bin/gp -f -q  == 1;

2012-03-28, 17:46   #24
bsquared

"Ben"
Feb 2007

23×163 Posts

Quote:
 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.

2012-03-28, 17:51   #25
bsquared

"Ben"
Feb 2007

23·163 Posts

Quote:
 Originally Posted by xilman FWIW, my update Perl script for the GCW tables runs Code: 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.

2012-03-30, 22:40   #26
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts

Quote:
 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?

2012-03-31, 02:38   #27
bsquared

"Ben"
Feb 2007

23×163 Posts

Quote:
 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.

 2012-04-01, 01:31 #28 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2012-04-01, 12:29 #29 Mathew     Nov 2009 35010 Posts 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()" 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.
 2012-04-01, 14:43 #30 bsquared     "Ben" Feb 2007 23·163 Posts I think there is a simple way to make everything relative to the binary location. I'll look into that.
 2012-04-10, 02:03 #31 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40P 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: Code: 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! ) Last fiddled with by Dubslow on 2012-04-10 at 02:04 Reason: close paren :)
2012-04-10, 03:45   #32
bsquared

"Ben"
Feb 2007

23·163 Posts

Quote:
 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.

2012-04-10, 06:20   #33
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

37·317 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ Programming 0 2018-11-01 14:57 Dubslow YAFU 4 2012-03-31 03:07 Xyzzy Lounge 23 2011-03-08 17:50 ixfd64 Software 10 2010-05-31 15:21 rogue GMP-ECM 4 2009-11-23 15:07

All times are UTC. The time now is 13:55.

Fri Mar 31 13:55:59 UTC 2023 up 225 days, 11:24, 0 users, load averages: 1.15, 1.05, 1.10