Reply With QuoteFirst, let me explain more clearly why P+1 factoring is probablistic. Here's from the GMP-ECM readme file
<snip>
</snip>Code:The P-1 method works well when the input number has a prime factor P such that P-1 is "smooth", i.e. has all its prime factor less or equal the step 1 bound B1, except one which may be less or equal the second step bound B2. For P=67872792749091946529, we have P-1 = 2^5 * 11 * 17 * 19 * 43 * 149 * 8467 * 11004397, so this factor will be found as long as B1 >= 8467 and B2 >= 11004397: $ echo 67872792749091946529 | ./ecm -pm1 -x0 2809890345 8467 11004397 GMP-ECM 5.0 [powered by GMP 4.1.2] [P-1] Input number is 67872792749091946529 (20 digits) Using B1=8467, B2=11004397, polynomial Dickson(6), x0=2809890345 Step 1 took 10ms Step 2 took 320ms ********** Factor found in step 2: 67872792749091946529 Found input number N There is no need to run several times P-1 with the same B1 and B2, like for ECM, since a factor found with one seed will be found by another one. The P+1 method works well when the input number has a prime factor P such that P+1 is "smooth". For P=4190453151940208656715582382315221647, we have P+1 = 2^4 * 283 * 2423 * 21881 * 39839 * 1414261 * 2337233 * 132554351, so this factor will be found as long as B1 >= 2337233 and B2 >= 132554351: $ echo 4190453151940208656715582382315221647 | ./ecm -pp1 -x0 2284918860 2337233 132554351 GMP-ECM 5.0 [powered by GMP 4.1.2] [P+1] Input number is 4190453151940208656715582382315221647 (37 digits) Using B1=2337233, B2=132554351, polynomial x^1, x0=2284918860 Step 1 took 3300ms Step 2 took 2460ms ********** Factor found in step 2: 4190453151940208656715582382315221647 Found input number N However not all seeds will succeed: only half of the seeds 's' work for P+1 (namely those where the Jacobi symbol of s^2-4 and P is -1.) Unfortunately, since P is usually not known in advance, there is no way to ensure that this holds. However, if the seed is chosen randomly, there is a probability of about 1/2 that it will give a Jacobi symbol of -1 (i.e. the factor P will be found if P+1 is smooth enough). A rule of thumb is to run 3 times P+1 with different random seeds.
So not only is it possible have a P+1 test fail because the seed was wrong, but it is also impossible to run enough seeds so that you are 100% sure it worked. In other words, runing 1 seed gives you a 50% chance of success, a second gives you 75%, a third 87.5%, etc.
It seems that our numbers may be able to avoid this probablistic nature somehow due to their unique form. The best thing would be if there were a seed that always worked for all proth numbers. This is kinda unlikely. Perhaps a seed can be calculated for individual proth numbers based on their k/n values that will always work. That's more likely to work. Failing those ideal cases, it seems possible that a pair of suitably dissimilar seeds could be found that would capture 50% of the the factors exclusively so that the sum is 100%. That would mean that two tests would be sufficient to prove the numbers are P+1 smooth.
In a simple attempt to see if there is some obvious way to make P+1 factoring non-probablistic for our numbers, I made a program to look for an approriate seed value that would always work for our factors. No real results yet. As expected, most give exactly 50% and when I combine the power of two values, they always seem to be 75% as well.
I think it is much more likely that the value will depend on a more intelligent rule that takes into account the k/n value being factored. Next I plan to analyze the data for values that fall into different residue classes mod 48.
If someone has any insight, feel free to join in the discussion.
-Louie
