B1/B2 values

[esakertt]

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.

[Dubslow]

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.)

[esakertt]

Originally Posted by Dubslow

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.