mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2012-11-12, 06:42   #1
esakertt
 
Oct 2012

B16 Posts
Unhappy B1/B2 values

In exponent info link, some B1/B2 values are shown for some exponents (P-1 tests). Without knowing about the P-1 tests and the theory behind them, I would ask how to use this B1/B2 information before the LL test ? Why this B1/B2 info is given ? I have not studied the P-1 tests.
esakertt is offline   Reply With Quote
Old 2012-11-12, 07:11   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

P-1 is an algorithm to attempt to factor a number.

In order to understand P-1, you need to understand smoothness of a number. That is, a number is n-smooth if all its prime factors are less than n. 100 is 5-smooth, as an example.

In order for P-1 to find a factor p of a number N, p-1 must be sufficiently smooth. Specifically, if p-1 is B1-smooth*, then the P-1 algorithm will find that p is a nontrivial factor of N. (Actually, all prime factors of of p-1 must be less than B1, with one exception; the one exception must be less than B2.) The higher the bounds, the more likely it is that p-1 is B1/B2-smooth, and thus the more likely it is to find a factor, but of course it also takes more work. Prime95 has a somewhat sophisticated algorithm to determine the bounds that have the most chance to find a factor per work done.

To be clear, B1 and B2 do not affect the LL test directly; the only correlation is, the higher B1/B2 are, the more likely that P-1 run was to find a factor.

(*Actually actually, p-1 must be B1-powersmooth, not just B1-smooth. That is, all prime powers of p-1 must be less than B1; as an example, 100 = 2^2 * 5^2 is not 5-[/i]power[/i]smooth but is 25-powersmooth.)

Last fiddled with by Dubslow on 2012-11-12 at 07:13 Reason: formatting
Dubslow is offline   Reply With Quote
Old 2012-11-14, 13:11   #3
esakertt
 
Oct 2012

11 Posts
Smile

Quote:
Originally Posted by Dubslow View Post
P-1 is an algorithm to attempt to factor a number.

In order to understand P-1, you need to understand smoothness of a number. That is, a number is n-smooth if all its prime factors are less than n. 100 is 5-smooth, as an example.

In order for P-1 to find a factor p of a number N, p-1 must be sufficiently smooth. Specifically, if p-1 is B1-smooth*, then the P-1 algorithm will find that p is a nontrivial factor of N. (Actually, all prime factors of of p-1 must be less than B1, with one exception; the one exception must be less than B2.) The higher the bounds, the more likely it is that p-1 is B1/B2-smooth, and thus the more likely it is to find a factor, but of course it also takes more work. Prime95 has a somewhat sophisticated algorithm to determine the bounds that have the most chance to find a factor per work done.

To be clear, B1 and B2 do not affect the LL test directly; the only correlation is, the higher B1/B2 are, the more likely that P-1 run was to find a factor.

(*Actually actually, p-1 must be B1-powersmooth, not just B1-smooth. That is, all prime powers of p-1 must be less than B1; as an example, 100 = 2^2 * 5^2 is not 5-[/i]power[/i]smooth but is 25-powersmooth.)
Thanks very much.
esakertt is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Timing for different B1 values? CRGreathouse GMP-ECM 8 2018-05-12 05:57
Erroneous values of s_n? CuriousKit Math 15 2016-01-31 11:57
reserving a few k values Trilo Riesel Prime Search 7 2015-09-27 23:20
reserving a few k values Trilo Riesel Prime Search 0 2013-08-25 14:47
98.00M to 98.05M Excluded Values storm5510 Lone Mersenne Hunters 45 2009-11-13 19:35

All times are UTC. The time now is 14:29.

Wed May 12 14:29:24 UTC 2021 up 34 days, 9:10, 0 users, load averages: 4.39, 3.50, 2.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.