Counter-examples, please

[Numbers]

Factorising numbers (or at least, determining whether or not they have factors) however you choose to do it, is a long and difficult process, especially for big numbers. Most methods (and I do not claim to be an expert on any of them) concentrate for rather obvious reasons on the number itself. It stands to reason, doesn’t it, if you want to factor z, you look at z? The idea of being able to factor z by looking at a number < z would, I imagine, be on most peoples wish list, and to be honest it is likely to remain there for some considerable time.

But it would seem (and I say seem with a very cautious voice because I am not making any great claim) that this wish may not be as far-fetched as we might suppose. Whilst looking at something completely unrelated to factoring I have noticed the following two relationships:

Let f(p) = p+( (p-1)/2)
Let p be prime such that f(p) is also prime
[a moments thought will reveal that this can only happen when p ends in 3]

then: HPF(6p – 2) = f(p)

Similarly, if we let g(q) = q+( (q+1)/2)
Let q be prime such that g(q) is also prime
[q must end in 7]

then: HPF(6q +2) = g(q)

A couple of numerical examples:
Let p = 32713, when f(p) = 49069, 6p - 2 = 196276 = 2 * 2 * 49069
Let q = 23447, when g(q) = 35171, 6q + 2 = 140684 = 2 * 2 * 35171

This means that if (z +/- 2)/6 is a prime of this form, you have a factor.

I have checked this for all p < 5*10^6 and it seems to hold. So if anyone can shed any light on why this might be true, or can find a counter-example, I would be very grateful.

[Numbers]

Its ok, I figured it out and should have done this before I posted.

4(p+(p-1)/2) = 4p +2p – 2

Apologies for wasting your bandwidth.

[axn]

HPF = Highest Prime Factor ?

As per you definition 4*f(p) = 6p-2, and 4*g(q) = 6q+2

Since your condition is "If f(p) is prime" and "If g(q) is prime", we know that 6p-2 and 6q+2 will factor as 2*2*f(p) and 2*2*g(q). Hence the result.

Or am I missing something?

EDIT:- Okay! Completely redundant posting

[ewmayer]

Originally Posted by Numbers

Factorising numbers (or at least, determining whether or not they have factors) however you choose to do it, is a long and difficult process, especially for big numbers. Most methods (and I do not claim to be an expert on any of them) concentrate for rather obvious reasons on the number itself. It stands to reason, doesn’t it, if you want to factor z, you look at z? The idea of being able to factor z by looking at a number < z would, I imagine, be on most peoples wish list, and to be honest it is likely to remain there for some considerable time.

Just to give one example, sieve-based factoring of numbers of certain convenient algebraic forms already does this. For instance, if we wish to see whether some number q is a factor of N = 2^p-1, we simply check whether 2^p == 1 modulo q using binary exponentiation, which involves no arithmetic quantities larger than q². This is an example of a factorization method whose complexity depends almost entirely on the size of the smallest factor of the number N, and only very weakly on the size of N. (The modular binary exponentiation needs O(log(p)) steps.)

Other examples of factorization methods whose asymptotic work requirements depend mainly on the size of the factor to be found include the p-1 and ECM algorithms. Unlike the above example of trial-factoring these require arithmetic modulo N and thus do depend more strongly on the size of N, but are still subexponential in N.

However, if we are speaking of *complete* factorization (rather than just finding small factors), the problem is that numbers such as the RSA keys are deliberately chosen to have smallest factors close to sqrt(N), and even your average random composite will have a penultimate factor that is not sufficiently smaller than N so as to allow that fact to be used to advantage.

[Numbers]

Thanks ewmayer.
It's amazing how these things go round in circles. I started out reading about modular arithmetic (specifically, computer implementation of), which led to an explanation of binary exponentiation on Chris Caldwell's website. Trying to figure out why that works led me to the discovery that started this thread. After I figured out the answer to that I found a paper by Peter Montgomery that explained its application in sieve-based factoring which has in turn led me back to looking at modular arithmetic. Connections, that's what learning math is about, making connections, and you guys are very good at pointing the way. Thank you.

BTW, I wasn't talking about *complete* factorisation, merely finding *a* factor to determine non-primality.