mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2012-03-28, 17:29   #23
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

101101110100012 Posts
Default

Quote:
Originally Posted by bsquared View Post
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;
I'm sure you could adapt it to your situation.
xilman is offline   Reply With Quote
Old 2012-03-28, 17:46   #24
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23×163 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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 is offline   Reply With Quote
Old 2012-03-28, 17:51   #25
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23·163 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
bsquared is offline   Reply With Quote
Old 2012-03-30, 22:40   #26
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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?
Dubslow is offline   Reply With Quote
Old 2012-03-31, 02:38   #27
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23×163 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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.
bsquared is offline   Reply With Quote
Old 2012-04-01, 01:31   #28
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

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.)
Dubslow is offline   Reply With Quote
Old 2012-04-01, 12:29   #29
Mathew
 
Mathew's Avatar
 
Nov 2009

35010 Posts
Default

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.
Mathew is offline   Reply With Quote
Old 2012-04-01, 14:43   #30
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23·163 Posts
Default

I think there is a simple way to make everything relative to the binary location. I'll look into that.
bsquared is offline   Reply With Quote
Old 2012-04-10, 02:03   #31
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default

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:
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 :)
Dubslow is offline   Reply With Quote
Old 2012-04-10, 03:45   #32
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23·163 Posts
Default

Quote:
Originally Posted by Dubslow View Post
... 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.
bsquared is offline   Reply With Quote
Old 2012-04-10, 06:20   #33
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

37·317 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ARM ASM request ET_ Programming 0 2018-11-01 14:57
Bug/request Dubslow YAFU 4 2012-03-31 03:07
Odd request? Xyzzy Lounge 23 2011-03-08 17:50
Prime95 featured in Maximum PC! ixfd64 Software 10 2010-05-31 15:21
GMP-ECM Request 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”