20051222, 08:42  #1 
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
Counterexamples, 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 farfetched as we might suppose. Whilst looking at something completely unrelated to factoring I have noticed the following two relationships: Let f(p) = p+( (p1)/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 counterexample, I would be very grateful. 
20051222, 09:11  #2 
Jun 2005
Near Beetlegeuse
388_{10} Posts 
Apologies
Its ok, I figured it out and should have done this before I posted.
4(p+(p1)/2) = 4p +2p – 2 Apologies for wasting your bandwidth. 
20051222, 09:12  #3 
Jun 2003
43×127 Posts 
HPF = Highest Prime Factor ?
As per you definition 4*f(p) = 6p2, and 4*g(q) = 6q+2 Since your condition is "If f(p) is prime" and "If g(q) is prime", we know that 6p2 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 20051222 at 09:13 
20051222, 19:59  #4  
∂^{2}ω=0
Sep 2002
República de California
2^{2}·2,939 Posts 
Quote:
Other examples of factorization methods whose asymptotic work requirements depend mainly on the size of the factor to be found include the p1 and ECM algorithms. Unlike the above example of trialfactoring 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 20051229 at 20:48 

20051229, 11:03  #5 
Jun 2005
Near Beetlegeuse
110000100_{2} 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 sievebased 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 nonprimality. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cheating at chess how to counter it  BrianE  Chess  73  20230118 18:10 
Reset the milestone counter: New SoB & PSP was found !!  Aillas  Prime Sierpinski Project  4  20161108 04:24 
Wiki Code Examples  amcfarlane  mersennewiki  6  20110216 12:36 
Visitor counter  Rodrigo  Forum Feedback  9  20100914 14:14 
A Counter example, anyone?  devarajkandadai  Math  27  20050524 04:37 