Register FAQ Search Today's Posts Mark Forums Read

 2005-12-22, 08:42 #1 Numbers     Jun 2005 Near Beetlegeuse 18416 Posts 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.
 2005-12-22, 09:11 #2 Numbers     Jun 2005 Near Beetlegeuse 1100001002 Posts 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.
 2005-12-22, 09:12 #3 axn     Jun 2003 2×3×5×173 Posts 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
2005-12-22, 19:59   #4
ewmayer
2ω=0

Sep 2002
República de California

22·3·7·139 Posts

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

 2005-12-29, 11:03 #5 Numbers     Jun 2005 Near Beetlegeuse 22·97 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Brian-E Chess 71 2019-07-15 14:10 Aillas Prime Sierpinski Project 4 2016-11-08 04:24 amcfarlane mersennewiki 6 2011-02-16 12:36 Rodrigo Forum Feedback 9 2010-09-14 14:14 devarajkandadai Math 27 2005-05-24 04:37

All times are UTC. The time now is 01:31.

Sat Dec 4 01:31:37 UTC 2021 up 133 days, 20 hrs, 0 users, load averages: 1.01, 1.54, 1.51