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.