mersenneforum.org Presentation and doubts with the application and competition of 100000000 prime digits
 Register FAQ Search Today's Posts Mark Forums Read

2022-05-05, 23:51   #23
Graph2022

May 2022

32 Posts

Quote:
 Originally Posted by Prime95 Welcome aboard. Prime95 can do a *probable* prime test on numbers of the for k*b^n+c where k,b,n,c are all "small". There are other programs that may or may not be able to prove those numbers prime depending on the values of k,b,n,c. There are no programs that can prove an arbitrary 100,000,000 digit number prime.
Hi. It is not possible to check if 100,000,000 digit is prime.
How quick is is to generate the number itself though? let's say 2^470,000,001 generates 100,000,000+ digit # ?

2022-05-06, 02:33   #24
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

1101100001002 Posts

Quote:
 Originally Posted by Prime95 Welcome aboard. Prime95 can do a *probable* prime test on numbers of the for k*b^n+c where k,b,n,c are all "small". There are other programs that may or may not be able to prove those numbers prime depending on the values of k,b,n,c. There are no programs that can prove an arbitrary 100,000,000 digit number prime.
Can Prime95 do a PRP test on general case (k*b^n+c)/gcd(k+c,b-1) (see my minimal prime problem)?

2022-05-06, 05:30   #25
paulunderwood

Sep 2002
Database er0rr

2·5·421 Posts

Quote:
 Originally Posted by Graph2022 Hi. It is not possible to check if 100,000,000 digit is prime. How quick is is to generate the number itself though? let's say 2^470,000,001 generates 100,000,000+ digit # ?
2^470000001 in binary is 1 followed by 470,000,001 zeroes. Using 64 bits per limb -- 7,343,751 limbs. How long does it take to allocate and zero (non static) memory of this many words when the speed of RAM is 2133 MT/s is .. erm... pretty fast

If you want to save its decimal representation to file then the bottleneck is there.

If you want to print it out it would depend on font size and the speed of your printer.

Last fiddled with by paulunderwood on 2022-05-06 at 05:34

2022-05-06, 06:48   #26
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

22·5·173 Posts

Quote:
 Originally Posted by Graph2022 Hi. It is not possible to check if 100,000,000 digit is prime.
Only trial division can be used (if the number has small prime factors, say < 2^32), e.g. large Fermat numbers and large double Mersenne numbers

However, if such large numbers are in fact primes, then this will not be proven in our lifetime (even if N-1 or/and N+1 can be trivially 100% factored), e.g. if the Fermat number F34 and/or the double Mersenne number MM127 are in fact primes, then they will not be proven prime (or PRP, e.g. 3-PRP) in our lifetime

Last fiddled with by sweety439 on 2022-05-06 at 06:53

2022-05-06, 08:20   #27
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

24·5·13 Posts

Quote:
 Originally Posted by sweety439 Can Prime95 do a PRP test on general case (k*b^n+c)/gcd(k+c,b-1) (see my minimal prime problem)?
Yes, PRP=k,b,n,c,"divisor", where divisor must be calculated manually. Please be aware that the quotation marks must remain in the worktodo entry. Please be also be aware that this is not feasible for very small numbers.

 2022-05-06, 12:03 #28 Dr Sardonicus     Feb 2017 Nowhere 73·17 Posts Algebraic factorization can also prove compositeness. If p and q are prime, 2^(p*q) - 1 has 2^p - 1 and 2^q - 1 as proper factors, regardless of whether these factors are prime. If p > 10^8 and q > 10^8, it might take a while to find factors of 2^(p*q) - 1 by trial division. Since 470000001 = 3*156666667, I can absolutely guarantee that 2^470000001 - 1 is composite. It has 2^3 - 1 = 7 as a prime factor, and 2^156666667 - 1 as a proper factor. The latter has the prime factor 90287940192103.
2022-05-06, 12:45   #29
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

346010 Posts

Quote:
 Originally Posted by Dr Sardonicus Algebraic factorization can also prove compositeness. If p and q are prime, 2^(p*q) - 1 has 2^p - 1 and 2^q - 1 as proper factors, regardless of whether these factors are prime. If p > 10^8 and q > 10^8, it might take a while to find factors of 2^(p*q) - 1 by trial division. Since 470000001 = 3*156666667, I can absolutely guarantee that 2^470000001 - 1 is composite. It has 2^3 - 1 = 7 as a prime factor, and 2^156666667 - 1 as a proper factor. The latter has the prime factor 90287940192103.
Well, my article has many examples of algebraic factorization and small prime factors, or the combine of them, to prove that a family contain no primes, some families require the combine of them, e.g. 8DDD...DDD in base 14, BBB...BBB9B in base 12, DDD...DDD5 in base 14, 1999...999 in base 17, 1666...666 in base 19, contain no primes (only count the numbers > base)

See my post for the factorization pattern for some families, to show that these families contain no primes (only count the numbers > base)

Also, when we sieve a given family (xyyy...yyyz in given base b, the family is (a*b^n+c)/gcd(a+c,b-1) for some integers a > 0 and c != 0, with gcd(a,c) = 1 and gcd(b,c) = 1), we delete the n such that (a*b^n+c)/gcd(a+c,b-1) have small prime factors (say < 2^32), as well as a*b^n+c has algebraic factorization (difference of squares, difference of cubes, Aurifeuillian factorization for x^4+4*y^4, ...)

Last fiddled with by sweety439 on 2022-05-06 at 12:49

2022-05-06, 13:40   #30
Dr Sardonicus

Feb 2017
Nowhere

10110110001112 Posts

Quote:
Originally Posted by sweety439
Quote:
 Originally Posted by Dr Sardonicus Algebraic factorization can also prove compositeness.
Well, my article has many examples of algebraic factorization
<snip>
Since you stated just a few posts back that
Quote:
 Originally Posted by sweety439 Only trial division can be used
I would say the fact stands proven, that you don't pay much attention to your own work.

 Similar Threads Thread Thread Starter Forum Replies Last Post Thecmaster GPU to 72 6 2019-03-22 07:21 Tamay82 Information & Answers 3 2018-09-08 16:34 paramveer Information & Answers 32 2012-01-15 06:05 ixfd64 Factoring 9 2010-09-21 19:39 ixfd64 Lounge 2 2004-11-05 23:42

All times are UTC. The time now is 10:25.

Sat Jul 2 10:25:18 UTC 2022 up 79 days, 8:26, 0 users, load averages: 1.46, 1.34, 1.34