mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-09-13, 18:03   #1
baih
 
baih's Avatar
 
Jun 2019

428 Posts
Default factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think)

2n1= a*b

factoring 2n-2 equivalent to factoring 2n-1

if this condition is met (a-1) divided by (b-1)
then 2n-1 =1 mod b-1


example
M11 = 0 mod 23 and 88 =0 mod 22
211-2 = 0 mod 22



M23 = 0 mod 47
223-2 = 0 mod 46





M73 = 0 mod 439
273-2 = 0 mod 438

M83 = 0 mod 167
283-2 = 0 mod 166

M131 = 0 mod 263
2131-2 = 0 mod 262

Last fiddled with by baih on 2020-09-13 at 18:42
baih is offline   Reply With Quote
Old 2020-09-13, 18:25   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by baih View Post
8<-----SNIP------

M29 = 0 mod 233
229-2 = 0 mod 232

8<-----SNIP------
Code:
(2^29-2)%232
174
paulunderwood is offline   Reply With Quote
Old 2020-09-13, 18:42   #3
baih
 
baih's Avatar
 
Jun 2019

2×17 Posts
Default

JUST arror because 2304167 MOD 232 not equal to n1
SO sory 29 is false


2n-1= a*b this condition is IF (a-1) divided by (b-1)

Last fiddled with by baih on 2020-09-13 at 18:52
baih is offline   Reply With Quote
Old 2020-09-14, 13:16   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×11×59 Posts
Default

If p is prime then 2p - 2 is divisible by 2p. So if q divides 2p - 1, gcd(q-1, 2p - 2) is divisible by 2p.

However, 2n - 2 is divisible by 2 but not by 4 if n > 1. If p is prime and the smallest prime factor q of 2p - 1 is congruent to 1 (mod 4), q-1 does not divide 2p - 2.

Consulting a table of factorizations of 2n - 1, I find that p = 29 (already noted) is the smallest p with this property. The next is p = 53 (q = 6361).
Dr Sardonicus is offline   Reply With Quote
Old 2020-09-17, 22:30   #5
baih
 
baih's Avatar
 
Jun 2019

2×17 Posts
Default

greatest common factor
its clear that for a composite numbre n = ab

n-1 divide gcf(a-1,b-1)


if gcf are a big numbre we can use it for factoring n

this what make the contruction of RSA numbre (beware) of making gcf small and does not help for factoring

example

n= 14111 = 103* 137
14110 = 0 MOD 34


and of course gcf(102,136) = 34

Last fiddled with by baih on 2020-09-17 at 22:35
baih is offline   Reply With Quote
Old 2020-09-17, 22:59   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

22ED16 Posts
Default

So

30526410117453380369827961 is a semi-prime
gcf(a-1,b-1) = 8 a free fact granted by me.

Does this help you find a and b?

n-1 = 2^3×5×17×5827×1288671127×5978327543
so the gcf could be any combination of 1 or more of those.
Uncwilly is online now   Reply With Quote
Old 2020-09-17, 23:06   #7
baih
 
baih's Avatar
 
Jun 2019

2×17 Posts
Default

no
becaus 8 very smal
i said earlier it needs to be very large to help
baih is offline   Reply With Quote
Old 2020-09-18, 00:03   #8
mathwiz
 
Mar 2019

100000012 Posts
Default

Quote:
Originally Posted by baih View Post
no
becaus 8 very smal
i said earlier it needs to be very large to help
http://factordb.com/index.php?query=2%5E1277-2 is fully factored. Are you saying you can therefore factor 2^1277-1?
mathwiz is offline   Reply With Quote
Old 2020-09-18, 01:51   #9
baih
 
baih's Avatar
 
Jun 2019

3410 Posts
Default

I DONT try to facto 2^1277-1 BY 2^1277-2
because i know the possibilty to find a large gcf(a-1,b-1) is very very small (excluded)
approximately the gcf < 10 digts it wont do anything if the factor is large

but this does not mean that the method is incorrect
baih is offline   Reply With Quote
Old 2020-09-21, 07:11   #10
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2×34 Posts
Red face

Quote:
Originally Posted by mathwiz View Post
http://factordb.com/index.php?query=2%5E1277-2 is fully factored. Are you saying you can therefore factor 2^1277-1?
I see an easy factorization of 2^n - 1 by induction: Suppose 2^(n-1) - 1 is factored. Then the factorization of 2^n - 2 is trivial. If we could somehow get the factorization from 2^n - 1 from that, ... /JeppeSN
JeppeSN is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49
P-1 factoring nuggetprime Riesel Prime Search 5 2007-04-14 22:25
ECM factoring michaf Sierpinski/Riesel Base 5 27 2006-10-31 03:19
low k/n factoring jasong Factoring 5 2005-10-05 07:18
Factoring 10^444 + 4 Yamato Factoring 1 2005-09-28 18:44

All times are UTC. The time now is 05:38.

Fri Dec 4 05:38:19 UTC 2020 up 1 day, 1:49, 0 users, load averages: 0.96, 0.92, 1.09

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