mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-05-30, 19:04   #1
CyD
 
May 2011

2 Posts
Default Fermat number and Modulo for searching divisors

Hello,

I try to find somebody who will be able to answer me about the following: I hope it is not too much trouble.
May be this property can be used for searching Fermat numbers divisors.
I know this forum is not for Fermat numbers, but may be, somebody is able to answer.
If you know a forum like this one where you think somebody is able to answer, please, let me know.


I demonstrate the following property (All numbers are natural numbers)
For a composite Fermat number , I suppose it is semi-prim (even if it is not semi-prim).
For example of semi-prim, I use a little number N, let it be equal to 105.
 N = 3*5*7=105
Here, N is not semi-prim because it has 3 divisors.
I choose to considerate N like a semi-prim event if it is not.
 N=D_1*D_2 Let  D_1 and  D_2 be  D_1=3 and  D_2 =35 or  D_1 = 5 and  D_2 = 21 or  D_1=7 and  D_2 = 15

About Fermat numbers :

Let define the 2 divisors of  F_m by  D_{m,1} and  D_{m,2} ,
and  X_m and  T_m by:  D_{m,1} = X_m.2^{m+2} +1 and  D_{m,2} = T_m.2^{m+2} +1

So, we have the following properties (for  i \leq i_{max} :
 2^{2^{n}-i.(m+2)} = - (-X)^i mod D_{m,1}
and in an equivalent way :
 2^{2^{n}-i.(m+2)} = - (-T)^i mod D_{m,2}
I try to find on the Internet some information about this property but I find nothing.

Do you know some internet sites or books about this property ?
Do you think this property can be used for searching Fermat numbers divisors?


If I'm not clear, please, let me know.

Many thanks by advance,
Best Regards,
Cyril Delestre
CyD is offline   Reply With Quote
Old 2011-05-30, 21:01   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by CyD View Post
Hello,

I try to find somebody who will be able to answer me about the following: I hope it is not too much trouble.
May be this property can be used for searching Fermat numbers divisors.
I know this forum is not for Fermat numbers, but may be, somebody is able to answer.
If you know a forum like this one where you think somebody is able to answer, please, let me know.


I demonstrate the following property (All numbers are natural numbers)
For a composite Fermat number , I suppose it is semi-prim (even if it is not semi-prim).
For example of semi-prim, I use a little number N, let it be equal to 105.
 N = 3*5*7=105
Here, N is not semi-prim because it has 3 divisors.
I choose to considerate N like a semi-prim event if it is not.
 N=D_1*D_2 Let  D_1 and  D_2 be  D_1=3 and  D_2 =35 or  D_1 = 5 and  D_2 = 21 or  D_1=7 and  D_2 = 15

About Fermat numbers :

Let define the 2 divisors of  F_m by  D_{m,1} and  D_{m,2} ,
and  X_m and  T_m by:  D_{m,1} = X_m.2^{m+2} +1 and  D_{m,2} = T_m.2^{m+2} +1

So, we have the following properties (for  i \leq i_{max} :
 2^{2^{n}-i.(m+2)} = - (-X)^i mod D_{m,1}
and in an equivalent way :
 2^{2^{n}-i.(m+2)} = - (-T)^i mod D_{m,2}
I try to find on the Internet some information about this property but I find nothing.

Do you know some internet sites or books about this property ?
Do you think this property can be used for searching Fermat numbers divisors?


If I'm not clear, please, let me know.

Many thanks by advance,
Best Regards,
Cyril Delestre
It is trivially known that any divisor p of 2^(2^n) + 1 must equal 1 mod
(2^(n+2)). I have given proofs on previous occasions. The proof
might be given as a homework problem in a first year number theory class.

This property is useful for trial division. It is often used to find small
divisors for large n. It isn't useful for much of anything else.

Last fiddled with by R.D. Silverman on 2011-05-30 at 21:01 Reason: typo
R.D. Silverman is offline   Reply With Quote
Old 2011-05-31, 08:16   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1102410 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It is trivially known that any divisor p of 2^(2^n) + 1 must equal 1 mod
(2^(n+2)). I have given proofs on previous occasions. The proof
might be given as a homework problem in a first year number theory class.

This property is useful for trial division. It is often used to find small
divisors for large n. It isn't useful for much of anything else.
It's also of historical interest because it was used to speed the factorization of F_7 by Pollard's rho algorithm.

Pollard's rho isn't really of much use these days now that ECM is available.

Paul
xilman is offline   Reply With Quote
Old 2011-05-31, 10:52   #4
CyD
 
May 2011

2 Posts
Default

I didn't try to prove that any divisor of  2^{2^{n}}+1 is like  X.2^{n+2}+1 . I know it's known.
I used it in order to demonstrate the following (with the same notation than my previous message)
 2^{2^{n}-i.(m+2)} = - (-X_m)^i mod D_{m,1}
and for example, if  2^{n} = 0 mod (m+2) and with  i_{max} = \frac{2^{n}}{m+2}
then  (-X_m)^{i_{max}} = -1 mod D_{m,1}
and if you have already prove it and if you know some internet site or book, I am interested by that.

Cyril
CyD is offline   Reply With Quote
Old 2011-05-31, 11:24   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CyD View Post
I didn't try to prove that any divisor of  2^{2^{n}}+1 is like  X.2^{n+2}+1 . I know it's known.
I used it in order to demonstrate the following (with the same notation than my previous message)
 2^{2^{n}-i.(m+2)} = - (-X_m)^i mod D_{m,1}
and for example, if  2^{n} = 0 mod (m+2) and with  i_{max} = \frac{2^{n}}{m+2}
then  (-X_m)^{i_{max}} = -1 mod D_{m,1}
and if you have already prove it and if you know some internet site or book, I am interested by that.

Cyril
I will quote Serge Lang.

Your notation sucks.

I can't be bothered wading through it. If you clean it up and repost
your comments, I will take a look.

Note, however, that trivially m+2 itself is a power of 2.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
HTML5 prime number searching? Dale Mahalko Software 7 2015-03-21 19:55
Looking for fermat divisors, n=90-120 firejuggler Prime Sierpinski Project 2 2012-01-10 17:14
Odds a largish number has N divisors? grandpascorpion Math 65 2006-02-16 15:20
Number of divisors of n? Citrix Math 10 2006-02-08 04:09
alright Fermat divisors, ya can run.... ixfd64 Lounge 9 2004-05-27 05:42

All times are UTC. The time now is 18:02.


Mon Nov 29 18:02:01 UTC 2021 up 129 days, 12:31, 0 users, load averages: 1.32, 1.35, 1.36

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.