mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Fermat number and Modulo for searching divisors (https://www.mersenneforum.org/showthread.php?t=15633)

 CyD 2011-05-30 19:04

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.
[TEX] N = 3*5*7=105 [/TEX]
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.
[TEX] N=D_1*D_2 [/TEX] Let [TEX] D_1 [/TEX] and [TEX] D_2 [/TEX] be [TEX] D_1=3 [/TEX] and [TEX] D_2 =35[/TEX] or [TEX] D_1 = 5 [/TEX] and [TEX] D_2 = 21 [/TEX] or [TEX] D_1=7 [/TEX] and [TEX] D_2 = 15 [/TEX]

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

So, we have the following properties (for [TEX] i \leq i_{max} [/TEX] :
[TEX] 2^{2^{n}-i.(m+2)} = - (-X)^i mod D_{m,1} [/TEX]
and in an equivalent way :
[TEX] 2^{2^{n}-i.(m+2)} = - (-T)^i mod D_{m,2} [/TEX]

Do you think this property can be used for searching Fermat numbers divisors?

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

Best Regards,
Cyril Delestre

 R.D. Silverman 2011-05-30 21:01

[QUOTE=CyD;262664]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.
[TEX] N = 3*5*7=105 [/TEX]
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.
[TEX] N=D_1*D_2 [/TEX] Let [TEX] D_1 [/TEX] and [TEX] D_2 [/TEX] be [TEX] D_1=3 [/TEX] and [TEX] D_2 =35[/TEX] or [TEX] D_1 = 5 [/TEX] and [TEX] D_2 = 21 [/TEX] or [TEX] D_1=7 [/TEX] and [TEX] D_2 = 15 [/TEX]

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

So, we have the following properties (for [TEX] i \leq i_{max} [/TEX] :
[TEX] 2^{2^{n}-i.(m+2)} = - (-X)^i mod D_{m,1} [/TEX]
and in an equivalent way :
[TEX] 2^{2^{n}-i.(m+2)} = - (-T)^i mod D_{m,2} [/TEX]

Do you think this property can be used for searching Fermat numbers divisors?

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

Best Regards,
Cyril Delestre[/QUOTE]

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.

 xilman 2011-05-31 08:16

[QUOTE=R.D. Silverman;262677]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.[/QUOTE]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

 CyD 2011-05-31 10:52

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

[SIZE=3][FONT=Calibri]Cyril[/FONT][/SIZE]

 R.D. Silverman 2011-05-31 11:24

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

[SIZE=3][FONT=Calibri]Cyril[/FONT][/SIZE][/QUOTE]

I will quote Serge Lang.