Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Digest Number 3672

Expand Messages
  • Kermit Rose
    ... Ok. You mean use a complex number as base instead of using a positive number as base. ... Ok. You mean that your exponents will be general positive
    Message 1 of 1 , Apr 7, 2013
    • 0 Attachment
      On 4/7/2013 7:33 AM, primenumbers@yahoogroups.com wrote:
      >
      > Message
      > ________________________________________________________________________
      > 1. A proposition for a better factorisation algorithm
      > Posted by: "bhelmes_1" bhelmes@... bhelmes_1
      > Date: Sat Apr 6, 2013 9:15 am ((PDT))
      >
      > A beautiful day,
      >
      > a very brief proposition for a better factorisation algorithm,
      > based on the basic ideas of Pollard p-1 algorithm
      >
      > 1. Instead of using N, take C

      Ok. You mean use a complex number as base instead of using a positive
      number as base.
      > a) Instead of an exponentation by primes, use only an exponentation by N

      Ok. You mean that your exponents will be general positive integers
      instead of being limited to primes.

      >
      > b) Choose natural numbers a(1) and b(1) not equal 0 for the start point

      ok. You mean that the complex number you start with must not have
      either part equal to zero. It is not a pure imaginary,
      or a pure real number. You do need to specify that the starting complex
      number is a complex integer.


      > c) Calculate a(n+1)+b(n+1)=(a(n)+b(n)I)^exponent mod f
      > where f is the composite number

      f is the positive composite integer to be factored.

      Here you mean that you are creating a sequence of exponentiations.

      Your starting complex number is a0 + b0 I

      a1 + b1 I is (a0 + b0 I)^e1

      a2 + b2 I is (a1 + b1 I)^e2

      etc


      Also, please tell us how the exponent sequence, e1, e2, e3, ...
      is determined.

      > d) calculate res=gcd (a(n+1), f) and res=gcd (b(n+1), f) not every time, but after 1000 exponentation for example.
      >
      > res gives the searched factor of f




      > e) You can store the value af a(1000*k) and b(1000*k)
      > if b(1000*(k+1))=0 you can recalculate the sequence
      > and make each time a gcd by every exponentation


      No, this is not the best re-calculation.

      What you need to do is:

      Suppose z0 is your starting complex number.

      All calculations are in mod f.

      z1 is z0^e1
      z2 is z1^e2
      z3 is z2^e3
      etc

      Then as you calculate the z's you also calculate the product of the z's
      mod f.

      w0 = 1
      z1 = z0^e1
      w1 = w0 * (z1 - 1)

      z2 = z1^e2
      w2 = w1 * (z2 - 1)

      z3 = z2^e3
      w3 = w2 * (z3 - 1)

      etc

      when w_k goes to zero,
      then apply GCD to w_(k-1).

      Otherwise take every 100 or 1000 or some other prechosen interval to
      apply the GCD. Which interval you choose will depend on the expected
      difficulty of the factoring.

      It would not be wise to choose an interval of 1000 if you expect the factor
      to be found in less than 100 iterations.






      > For the second part of Pollard p-1 you could use a lattice instead of searching linear which can be done on a cluster
      >
      > 2. Instead of using N, use the field of adjoined square
      > a+b*sqrt (A) where A is a non quadratic residuum mod f

      On the average it would not matter whether you chose quadratic residue
      or non quadratic residue
      because:

      Suppose f = x y where x and y are prime.

      If you want a quadratic non-residue, you would want the quadratic
      non-residue to be with respect to x or y.
      Since you do not yet know x are y, it is not possible to chose a
      quadratic non-residue for them.


      If you chose a non-quadratic residue with respect to f,
      then it would be a quadratic residue with respect to one of x,y
      and a quadratic non-residue with respect to the other factor.


      > same algorithm as before
      >
      > 3. Instead of using N, use the field of complex adjoined square
      > a+b*sqrt(A)I where A is a non quadratic residuum mod f
      >
      > same algorithm as before
      >
      > You can execute 1.,2. and 3. parallel.

      You could do your steps 2 and 3 is parallel.

      The standard second part of the (p-1) algorithm cannot be started until
      the first part is completed.


      > Nice greetings from the primes
      > Bernhard
      >
      >
      >

      Kermit
    Your message has been successfully submitted and would be delivered to recipients shortly.