Talk:Pollard's p − 1 algorithm

[Untitled]

a^(p-1) = 1 mod (p) for a in U*(Z/nZ) is meaningless and is not the correct statement of fermat's little theorem.

I don't think you really understand the meaning of the notation. For starters mod is an equivalence relation on Z and

a^(p-1) = 1 mod (p) means

[a^(p-1) -1] / p = 0

But when you say that a is in U*(Z/nZ) then what does it mean to divide an element of U*(Z/nZ) by the integer p?

Fermat's little theorem does say that for all a!

a^(p-1) = 1 mod (p)

I don't know what you're trying to say ,but it's not fermat's little theorem and it's mathematically ungramatical.

First of all Fermat's little theorem isn't stated in its verbatim form for a reason. However it's a short hop from FLT to the statement in the article, and the statement in the article is correct.

The notation YOU are using isn't standard, although you may think it correct. a^(p-1) = 1 mod (p) is not valid notation. To indicate the equivalence you need to use ≡ (note: three lines) and (mod p) (note: parentheses surrounding the whole thing). To indicate a computation you would simply use = (note: two lines) and mod p (note: no parentheses).

Lastly, Fermat's little theorem doesn't say that for all a that "a^(p-1) = 1 mod (p)", there is a condition that a has to be coprime to p. For instance, if you picked a and p to be the same value then the equation is wrong (as I mentioned in the summary when I reverted your change before). CryptoDerk 01:45, Oct 22, 2004 (UTC)

Well it doesn't really matter, say whatever you like. Nobody is going to rely on this entry for anything.

Prime factors?

"It is possible that all the prime factors of n are divisible by small primes, at which point the Pollard p-1 algorithm gives you n again."

If a prime factor is divisible by a small prime.... how is it a prime factor? —Preceding unsigned comment added by 129.97.22.119 (talk) 23:53, 11 February 2008 (UTC)

I think the mistake is between P being a prime factor and P-1 being divisible by a small prime. The quoted statement is an error. It needs to be worded differently. Robomojo (talk) 09:14, 31 May 2008 (UTC)

One large factor variant

In what way does FFT help? Can it be used to accelerate the process of searching over many primes or only for asymptotically fast multiplication? If it's the latter, it should be stated that this is only effective for very large N. — Preceding unsigned comment added by 129.55.200.20 (talk) 14:58, 14 August 2012 (UTC)

Basically, only the fact that if you choose a second bound, B2, such that a single factor of N is between B1 and B2 and all other below B1, then there is a memory-intensive algorithm that could do the factoring. Everything else in the article is very unclear. Aeris-chan (talk) 20:27, 20 December 2009 (UTC)

Not entirely sure, but this page seems to be pointing out only powers of primes. While x^2 is a power of x many algorithms actually perform x^p-1 or some other variable exponent, which is costly.

Consider, the following which contains a powermod for each multiplication

Public Shared Function pMinusOneFactor(ByVal n As BigInt) As BigInt
       Dim rand As New Random()
       Dim power As BigInt = 1
       Dim residue As BigInt = lnr(rand.Next, n)
       Dim test As BigInt = residue - 1
       Dim gcd As BigInt = BigInt.Gcd(test, n)
       Dim Count As Integer = 0
       While True
           While gcd = 1
               power += 1
               If Count = 9999 Then
                   Console.WriteLine(power)
                   Count = 0
               Else
                   Count += 1
               End If
               residue = residue.PowerMod(power, n)
               test = residue - 1
               gcd = BigInt.Gcd(test, n)
           End While
           If gcd.Equals(n) Then
               power = 1
               residue = residue.PowerMod(power, n)
               test = residue - 1
               gcd = BigInt.Gcd(test, n)
           Else
               Return gcd
           End If
       End While
       Return Nothing
   End Function

Then there is this variant, which performs only a few multiplications instead of powering, which at best can be done with repeated squaring.

Function PollardP1(ByVal Value As BigInt, Optional ByVal limit As Integer = -1) As BigInt
       Dim a, b, t, p, m, c As BigInt
       m = Value
       a = 1
       Dim sqrt As BigInt = Value.Sqrt
       Dim rand As New Random
      
       Do
           b = 1
           t = 1
           While t = 1
               p = 1
               For I As Integer = 1 To 20
                   a = (a * a + 1) Mod m
                   b = (b * b + 1)
                   b = (b * b + 1) Mod m
                   If a > b Then
                       c = a - b
                   Else
                       c = b - a
                   End If
                   p = (p * c) Mod m
                   If p = 0 Then
                       Dim Ga As BigInt = BigInt.Gcd(a, m)
                       If Ga <> 1 AndAlso Ga <> m Then
                           Console.WriteLine("{0} * {1} = {2}", Ga, m / Ga, Value)
                           Return Ga
                       End If

                       Dim Gb As BigInt = BigInt.Gcd(b, m)
                       If Gb <> 1 AndAlso Gb <> m Then
                           Console.WriteLine("{0} * {1} = {2}", Gb, m / Gb, Value)
                           Return Gb
                       End If
                       Dim Gc As BigInt = BigInt.Gcd(c, m)
                       If Gc <> 1 AndAlso Gc <> m Then
                           Console.WriteLine("{0} * {1} = {2}", Gc, m / Gc, Value)
                           Return Gc
                       End If
                       Exit For
                   End If
               Next
        
               t = BigInt.Gcd(p, m)
           End While
           If t Mod m = 0 Then ' failed again, try with new seed of a
               Do
                   a = rand.Next Mod srt
               Loop While a < 2
           Else
               Console.WriteLine("{0} * {1} = {2}", t, m / t, Value)
               Return m / t
           End If
           
           If Not limit = -1 AndAlso attempts > limit Then
               return -1
           End If
       Loop
   End Function

While the first version may find small primes faster, the second is more efficient for large primes. Especially if you are using O(n^2) multiplication and division.

In any case once you are dealing with primes this large, its probably time to switch to another algorithm.

Alexander Higgins —Preceding unsigned comment added by 68.46.132.117 (talk) 09:23, 20 March 2010 (UTC)

Base concepts

This section shows the basic formula as a^K(p-1) (left-hand side)... but then does nothing but reference x in explanation. I read this as x is a, but making that assumption is out of my league. Either one of things should probably happen: a) the forumla should reflect x, b) x should change to the proper variable, or c) an explanation of an x that is implicit and transcendent of the equation should be explained (I don't think that's what's going on here to be clear). I am definitely not qualified to make this change. 2601:204:C001:27E0:0:0:0:480 (talk) 03:57, 2 September 2021 (UTC)