Example
With N=112729 and A=5, successive values of are:
- V1 of seq(5) = V1! of seq(5) = 5
- V2 of seq(5) = V2! of seq(5) = 23
- V3 of seq(23) = V3! of seq(5) = 12098
- V4 of seq(12098) = V4! of seq(5) = 87680
- V5 of seq(87680) = V5! of seq(5) = 53242
- V6 of seq(53242) = V6! of seq(5) = 27666
- V7 of seq(27666) = V7! of seq(5) = 110229.
At this point, gcd(110229-2,112729) = 139, so 139 is a non-trivial factor of 112729. Notice that p+1 = 140 = 22 × 5 × 7. The number 7! is the lowest factorial which is multiple of 140, so the proper factor 139 is found in this step.
Using another initial value, say A = 9, we get:
- V1 of seq(9) = V1! of seq(9) = 9
- V2 of seq(9) = V2! of seq(9) = 79
- V3 of seq(79) = V3! of seq(9) = 41886
- V4 of seq(41886) = V4! of seq(9) = 79378
- V5 of seq(79378) = V5! of seq(9) = 1934
- V6 of seq(1934) = V6! of seq(9) = 10582
- V7 of seq(10582) = V7! of seq(9) = 84241
- V8 of seq(84241) = V8! of seq(9) = 93973
- V9 of seq(93973) = V9! of seq(9) = 91645.
At this point gcd(91645-2,112729) = 811, so 811 is a non-trivial factor of 112729. Notice that p-1 = 810 = 2 × 5 × 34. The number 9! is the lowest factorial which is multiple of 810, so the proper factor 811 is found in this step. The factor 139 is not found this time because p-1 = 138 = 2 × 3 × 23 which is not a divisor of 9!
As can be seen in these examples we don't know in advance whether the prime that will be found has a smooth p+1 or p-1.
Read more about this topic: Williams' P + 1 Algorithm
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)