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

Question on residues (and Legendre?)...

Expand Messages
  • David Cleaver
    Hello all, I m trying to come up with a new factoring method (what else is new!) but I am having troubles with some (alot?) of the ground work. My current
    Message 1 of 1 , Jul 1, 2002
    • 0 Attachment
      Hello all,

      I'm trying to come up with a new factoring method (what else is new!)
      but I am having troubles with some (alot?) of the ground work. My
      current problem is this:

      Lets say I wanted to compute x^6 == a (mod n) and I wanted to find out
      if "a" was divisible by a prime, p, without doing trial division and
      also only by looking at x (not raising it to the 6-th power).

      Let me show you a snippet of a paper that I have downloaded and maybe
      then you can see where I'm going.
      ========================================================
      f(x) = (x + floor(sqroot(n)))^2 - n
      from this we get:
      f(x) == (x + floor(sqroot(n)))^2 (mod n)
      We want f(x) = p1^k1 * p2^k2 * ... * pn^kn where p1,p2,...,pn are all
      small primes. Therefore a prime, pi, in our factor base divides f(x).
      We also know that pi does not divide n (we trial divide first to make
      sure). After looking at the polynomial we are working with, we see that
      this implies* the following result:

      n == (x + floor(sqroot(n)))^2 (mod pi)
      [*question from me: is this really implied?]

      This means that n must be a quadratic residue mod pi and thus our factor
      base should only consist of primes, pi, such that n is a quadratic
      residue mod pi.

      Since n is a quadratic residue mod p, this means that it is either:
      n == t^2 mod p or n == (-t)^2 mod p.
      This also means that (x + floor(sqroot(n))) must be congruent to t or -t
      mod p.
      ========================================================

      I'm trying to apply the above logic to the 6-th power instead of just
      the 2-nd power. I know for the Quadratic Sieve we choose the primes p
      to be the ones such that the Legendre symbol (n/p) = 1. I guess I'm
      having difficulty in getting an equivalent test for the 6-th power
      case. Anyone have any ideas?

      I thought the test would be a simple a^((p-1)/6) =?= 1 (mod p) when p
      was of the form 6k+1, but it didn't seem to work on a random test case I
      worked out by hand. Let me show you:
      n = 14017, p = 7
      x^2 == 14017 (mod 7)
      a^((p-1)/2) =?= 1 (mod p)
      14017^3 =?= 1 (mod 7) false, b/c 14017^3 == 6 (mod 7)
      ie, its not a quadratic residue mod 7...

      x^3 == 14017 (mod 7)
      a^((p-1)/3) =?= 1 (mod p)
      14017^2 =?= 1 (mod 7) false, b/c 14017^2 == 2 (mod 7)
      ie, its not a cubic residue mod 7...

      x^6 == 14017 (mod 7)
      a^((p-1)/6) =?= 1 (mod p)
      14017^1 =?= 1 (mod 7) false, b/c 14017^1 == 3 (mod 7)
      ie, its not a sextic residue mod 7...

      So, if I'm applying this right, it looks like 7 shouldn't divide any
      x^6 == a (mod n) but,
      21^6 == 10115 (mod 14017) 10115=5*7*17^2
      23^6 == 2352 (mod 14017) 2352=2^4*3*7^2
      30^6 == 3864 (mod 14017) 3864=2^3*3*7*23

      So, can anyone see what I'm doing wrong? Is the "source" I'm basing
      most of this on wrong? Can anyone see how I might be able to go about
      solving this problem? I'd also like to know how to find this new
      Legendre [shall we call it Legendre-6] of (n/p) when p is in
      {2, 3, or of the form 6k + 5}. I think this last part will be more
      difficult than when p = 6k + 1, but then again, I'm just a newbie so
      it's probably all just very easy and I can't see it yet. ;)
      Well, I'd like to say thank you in advance for any help that can be
      provided.

      -David C.
    Your message has been successfully submitted and would be delivered to recipients shortly.