mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2005-12-22, 08:42   #1
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default Counter-examples, please

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 is offline   Reply With Quote
Old 2005-12-22, 09:11   #2
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default Apologies

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.
Numbers is offline   Reply With Quote
Old 2005-12-22, 09:12   #3
axn
 
axn's Avatar
 
Jun 2003

2·32·7·37 Posts
Default

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

Last fiddled with by axn on 2005-12-22 at 09:13
axn is offline   Reply With Quote
Old 2005-12-22, 19:59   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

32×5×11×23 Posts
Default

Quote:
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 = 2p-1, we simply check whether 2p == 1 modulo q using binary exponentiation, which involves no arithmetic quantities larger than q2. 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.

Last fiddled with by ewmayer on 2005-12-29 at 20:48
ewmayer is offline   Reply With Quote
Old 2005-12-29, 11:03   #5
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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.
Numbers is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cheating at chess how to counter it Brian-E Chess 71 2019-07-15 14:10
Reset the milestone counter: New SoB & PSP was found !! Aillas Prime Sierpinski Project 4 2016-11-08 04:24
Wiki Code Examples amcfarlane mersennewiki 6 2011-02-16 12:36
Visitor counter Rodrigo Forum Feedback 9 2010-09-14 14:14
A Counter example, anyone? devarajkandadai Math 27 2005-05-24 04:37

All times are UTC. The time now is 14:54.

Tue Aug 4 14:54:18 UTC 2020 up 18 days, 10:41, 0 users, load averages: 1.93, 1.52, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.