20061125, 16:36  #1 
Bronze Medalist
Jan 2004
Mumbai,India
804_{16} Posts 
FLT and Binomials
Is there a method of utilising Fermat's little theorem and the Binomial theorem and factorising large numbers. Is it well known and widely used? Mally 
20061129, 15:21  #2 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
An algorithm for primes.
An Algorithm for determining primes. Since I have not received any response on this thread I give below a method to determine primes. Kindly examine it for whatever merit it contains and whether it can be successfully used for determining primes. First of all a ready table of primes should be available at our disposal. Lets say we have one up to 2^30. For simplicity lets determine the primality of a known prime say 641. Using FLT then 2^(6411)1 is completely divisible by 641. Hence 2^640 – 1 = (2^320 +1) ( 2^320  1 ) Now 2^320 = (2^32)^10 = [(1073741824) x 2^2]^10 Because 2^30 = 1073741824 (available). Let us express 17373741824 in units of 641 or in multiples of 641 as we are testing the divisibility of the expression by 641. Now 1073741824 = (1675104)x 641 + 160. Let us denote ALL the multiples of 641 by the letter N. As we proceed N will take different values which for simplicity we will consider as N all the time. Therefore 1073741824 = [(N + 160.) x 2^2 ]^10 =(4N + 640)^10. BY simplifying the expression we get (N+N1)^10. Since N +N is a multiple this boils down to (N  1) Therefore 2^320 + 1 = (N1)^10 + 1 2^320 – 1 = (N – 1)^10 1 Hence (2^640) – 1 = (N 1)^20 – 1. Now all the terms of the binomial expansion except the last term has N as part of the coefficient. So all these terms are divisible by 641. The last term is 1^20 which cancels with 1 out side the expansion. So we conclude that 2^640 – 1 is divisible by 641. Therefore 641 is a prime number. Mally 
20061129, 16:15  #3  
Tribal Bullet
Oct 2004
3^{3}·131 Posts 
Quote:
Also, wouldn't the last line of your proof be fooled by Carmichael numbers? jasonp Last fiddled with by jasonp on 20061129 at 16:17 

20061130, 04:29  #4  
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
Factorisation of N1
Quote:
To your second, Im not sure but I woud say probably, as its based on the FLT and if you can fool FLT so can you do so by Carmichael numbers. Good questions ! jasonp. Mally : 

20061203, 09:48  #5 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
Another worked example
Another worked example. Since my last example was a bit laborious and confusing I give another example. Let us test whether 524287 is a prime number or not. If it is then it must satisfy 2^(524287 1) = 1 mod 524287. Now from prime tables 2^19 = 524288. If we express this no. in terms of our number 524287 (call it N in this case ) We have 2^19 = N + 1 (Where N is 524287 or a multiple , here it is 1x 524287) Now 2^ (524287 – 1) – 1 = 2 ^ (524286) 1 This is (2^ 262143 + 1) (2^262143 – 1) [ a^2 – b^2 = (a+b)(ab) ] The exponent 262143 = (2^19)^ 13797 = (N + 1) ^13797 Because when 262143 is divided by 19 the answer is 13797. There fore (2^19)^13797 + 1 = (N + 1) ^ 13797 + 1 (2^19)^13797 – 1 = (N + 1) ^ 13797  1 Therefore (2^19)^13797 = (N + 1)^ 13797 By squaring the above expression and subtracting 1 Therefore 2^ 524286  1 = (N + 1) ^ 27594 – 1 [524286 = 19 x 13797 x 2 ] = (N + 1) ^27594  1 The last term of the binomial expansion is + 1 (from N + 1) and this cancels with – 1 in the expression itself All the other terms of (N +1) ^27594 have N as part of the coefficients and hence are divisible by 524287 . So we have 2 ^ (524287 – 1 ) = = 1 mod 524287. Hence 524287 is a prime as per the FLT. Mally 
20061203, 13:54  #6  
Jun 2005
lehigh.edu
2^{10} Posts 
primality /ne factoring
Quote:
were moved to "math" or somewhere else more appropriate. Primality (proofs) are a completely different topic (runs in polyn time, most likely polyn of degree 4, definitely degree 4 for expected runtime); while factoring is believed to be hard [presuming P /ne NP]. In any case, best known method is subexponential, for factoring. That would be gnfs, cf. RSA155=RSA512, and the more recent RSA200. Likewise, if we were considering primality here, the current record for proof of a (random) prime is 20,000 digits (up from 15,000, both by the same person/group as RSA200). You don't seem to be addressing questions of runtime, of the type needed to scale your proposed method up to the current range of interest. bd (dept math, lehigh) 

20061204, 07:29  #7 
Bronze Medalist
Jan 2004
Mumbai,India
2052_{10} Posts 
Redirection of thread
[QUOTE=bdodson;93093]Not to quibble, but you might have better luck if this thread
were moved to "math" or somewhere else more appropriate. QUOTE] Thank you bdodson for the suggestion of redirecting my thread to the math forum. Typical beaucracy! Moderator please do the needful. I am not sure what you mean by 'better luck' I am just an amateur mathematician and by no means an all rounder. As such I have no knowledge of programming and have no desire of ever attaining it. Have you gone thru my worked examples to realise the potentiality of it? I have merely given an algortihm and if you dont consider it as such lets call it a mathematical curiousity. It is not the creation of a crank as I have resurrected this method by a respected Indian PhD who may have gone into obscurity had I not written about it. ( name witheld) The reason why I have submitted it is to explore the possibility of working out a much shorter version as compared to the existing systems. I would add that if you can represent M44 then there is no reason why M45 cannot be cracked out by this algorithm. In our quest as the aim of GIMPS I request you dont dismiss this system lightly. BTW: I am not impressed by your programming jargon and would have prefered an honest opinion with some worthwhile facts why this algortihm does not work and cannot be applied. Remember Gimps is here to break records not cite the existing ones! Mally 
20061204, 13:44  #8  
Jun 2005
lehigh.edu
10000000000_{2} Posts 
[QUOTE=mfgoode;93150]
Quote:
fit the usual definition on amateur either. In particular, you've completely missed the point of my comment. I don't program either. Runtime analysis is part of computational number theory; independent of coding. Quote:
first note  your description of the method shows no awareness of the present state of research in primality testing. And besides, you're posting in a "factoring" thread. The difference between the difficulty of the problems should be clear to anyone with just a small amount of attention. Those of us interested in factoring have just managed to reach 200decimaldigits (rsa200), a record that replaced several intermediate records, including RSA155, at 512bits. Professionals in primality testing proved the primality of a 20,000digit prime ("random", not mersenne or other special form), replacing their earlier benchmark of 15,000 digits. The difference is math, not coding. The complexity of the algorithm. The term "polynomial vs subexponential" refers to the number of computations needed to find the result. Quote:
the main mersenne web page (not this forum), you'll see that factoring; in particular factoring Cunningham and related numbers; ... Ah. Maybe not. We're listed under "Miscellaneous", then "links". The page I'm attempting to refer to is http://www.mersenne.org/ecm.htm With the exception of the Fermat numbers, all of the factoring questions involve numbers with no more than 1200bits, no more than 384decimaldigits for the largest unfactored Cunningham. No 9million digit primes, we're looking for 70digit (ecm) or perhaps 100digit (gnfs) primes. 'Cause our problem is more difficulty than proving primality, at 20000digits (random primes) or 10milliondigits (mersenne). You've wandered into a thread where the problems are different. And the expertise needed to evaluate the algorithms are different also. I'm requesting again that you wander elsewhere. B. Dodson 

20061204, 17:34  #9  
Bronze Medalist
Jan 2004
Mumbai,India
100000000100_{2} Posts 
[QUOTE=bdodson;93170]
Quote:
Thank you for your attention B. Dodson. You are right and I have mistakenly wandered into a factoring thread when my algorithm does not deal with factoring, at most one or two divisions, to prove the primality or not of a number, beyond doubt. I will take your advice and I request the moderator of this thread to please move it to the Math forum so I can open shop therein Thank you once again, Mally 

20061204, 22:54  #10 
"William"
May 2003
New Haven
3×787 Posts 
Mally,
If I understand correctly, you have stumbled onto what is known as a Fermat Probable Prime test, augmented with suggestions about how to perform the modulo that are well suited for hand calculation. Unfortunately, you have read Fermat's Little Theorem backwards, and you do not have a proof of primality: for any prime it is true that a^(p1) = 1 mod p, but for every choice of "a" there are also some composites for which a^(n1) = 1 mod n. Try googling PRP and/or "Probable Prime" for more information. Also check out Strong Probable Prime or SPRP  this improves the PRP test by observing that as long as k is even, you can factor a^k1 as a difference of squares, and that if p is prime, it must divide one of these. Many composites that return false positives to the PRP test will fail the SPRP test because n=a*b, but a divides one of the terms and b divides a different term, so n divides the product, but not any individual term. 
20061204, 23:26  #11  
Aug 2002
Buenos Aires, Argentina
1352_{10} Posts 
Quote:
All congruences below are modulo . We trivially find that Now we will compute: Since all factors of have the form we know that So or According to your criterion any Mersenne number is prime. 
