## Question on residues (and Legendre?)...

Expand Messages
• 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.