mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-11-25, 16:36   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

80416 Posts
Question 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
mfgoode is offline   Reply With Quote
Old 2006-11-29, 15:21   #2
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Lightbulb 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^(641-1)-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+N-1)^10.
Since N +N is a multiple this boils down to (N - 1)
Therefore 2^320 + 1 = (N-1)^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
mfgoode is offline   Reply With Quote
Old 2006-11-29, 16:15   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33·131 Posts
Default

Quote:
Originally Posted by mfgoode View Post

An Algorithm for determining primes.

For simplicity lets determine the primality of a known prime say 641.
When trying to prove the primality of N, wouldn't this method require the factorization of N-1?

Also, wouldn't the last line of your proof be fooled by Carmichael numbers?

jasonp

Last fiddled with by jasonp on 2006-11-29 at 16:17
jasonp is offline   Reply With Quote
Old 2006-11-30, 04:29   #4
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Thumbs up Factorisation of N-1

Quote:
Originally Posted by jasonp View Post
When trying to prove the primality of N, wouldn't this method require the factorization of N-1?

Also, wouldn't the last line of your proof be fooled by Carmichael numbers?

jasonp
To your 1st question NO! thats the beauty of the algorithm.

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 :
mfgoode is offline   Reply With Quote
Old 2006-12-03, 09:48   #5
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Thumbs up 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)(a-b) ]

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
mfgoode is offline   Reply With Quote
Old 2006-12-03, 13:54   #6
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default primality /ne factoring

Quote:
Originally Posted by mfgoode View Post

Another worked example.

Since my last example was a bit laborious ...
Hence 524287 is a prime as per the FLT.

Mally
Not to quibble, but you might have better luck if this thread
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)
bdodson is offline   Reply With Quote
Old 2006-12-04, 07:29   #7
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

205210 Posts
Thumbs down Re-direction 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
mfgoode is offline   Reply With Quote
Old 2006-12-04, 13:44   #8
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

100000000002 Posts
Default

[QUOTE=mfgoode;93150]
Quote:
Originally Posted by bdodson View Post
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.
I gave up my amateur status in 1976. You, OTOH don't seem to
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:
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.
No. I'm not immediately interested, for the reason explained in my
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 200-decimal-digits (rsa-200), a record that replaced several
intermediate records, including RSA-155, at 512-bits. Professionals
in primality testing proved the primality of a 20,000-digit 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:
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
My honest opinion is that your posts are off-topic. If you scan through
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 1200-bits, no more than
384-decimal-digits for the largest unfactored Cunningham. No 9-million
digit primes, we're looking for 70-digit (ecm) or perhaps 100-digit (gnfs)
primes. 'Cause our problem is more difficulty than proving primality, at
20000-digits (random primes) or 10-million-digits (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
bdodson is offline   Reply With Quote
Old 2006-12-04, 17:34   #9
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

1000000001002 Posts
Arrow

[QUOTE=bdodson;93170]
Quote:
Originally Posted by mfgoode View Post

I gave up my amateur status in 1976. You, OTOH don't seem to
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.
~ ~ ~
No. I'm not immediately interested, for the reason explained in my
first note -- 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

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
mfgoode is offline   Reply With Quote
Old 2006-12-04, 22:54   #10
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default

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^(p-1) = 1 mod p, but for every choice of "a" there are also some composites for which a^(n-1) = 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^k-1 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.
wblipp is offline   Reply With Quote
Old 2006-12-04, 23:26   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

135210 Posts
Default

Quote:
Originally Posted by mfgoode View Post

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.
According to your proof all Mersenne numbers with prime exponents are prime.

All congruences below are modulo 2^p-1.

We trivially find that 2^p \eq 1

Now we will compute: 2^{2^p-1} \,\pmod {2^p-1}

Since all factors of 2^p-1 have the form 2kp+1 we know that 2^p-1 \eq 1 \,\pmod p

2^{2^p-1} \eq 2^{m*p+1} \eq 2*(2^p)^m \eq 2*1^m \eq 2

So 2^{2^p-1} \eq 2 or 2^{2^p-2} \eq 1

According to your criterion any Mersenne number is prime.
alpertron is offline   Reply With Quote
Reply

Thread Tools


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

Thu May 6 14:00:42 UTC 2021 up 28 days, 8:41, 1 user, load averages: 2.15, 2.20, 2.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.