mersenneforum.org factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-13, 18:03 #1 baih     Jun 2019 2·17 Posts 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
2020-09-13, 18:25   #2
paulunderwood

Sep 2002
Database er0rr

2·1,723 Posts

Quote:
 Originally Posted by baih 8<-----SNIP------ M29 = 0 mod 233 229-2 = 0 mod 232 8<-----SNIP------
Code:
(2^29-2)%232
174

 2020-09-13, 18:42 #3 baih     Jun 2019 2·17 Posts 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
 2020-09-14, 13:16 #4 Dr Sardonicus     Feb 2017 Nowhere 67638 Posts 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).
 2020-09-17, 22:30 #5 baih     Jun 2019 2×17 Posts 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
 2020-09-17, 22:59 #6 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 7·29·43 Posts 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.
 2020-09-17, 23:06 #7 baih     Jun 2019 2×17 Posts no becaus 8 very smal i said earlier it needs to be very large to help
2020-09-18, 00:03   #8
mathwiz

Mar 2019

22×52 Posts

Quote:
 Originally Posted by baih 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?

 2020-09-18, 01:51 #9 baih     Jun 2019 3410 Posts 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
2020-09-21, 07:11   #10
JeppeSN

"Jeppe"
Jan 2016
Denmark

25×5 Posts

Quote:
 Originally Posted by mathwiz 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

 Similar Threads Thread Thread Starter Forum Replies Last Post xx005fs GPU Computing 3 2018-10-27 14:49 nuggetprime Riesel Prime Search 5 2007-04-14 22:25 michaf Sierpinski/Riesel Base 5 27 2006-10-31 03:19 jasong Factoring 5 2005-10-05 07:18 Yamato Factoring 1 2005-09-28 18:44

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

Sun Oct 25 02:09:48 UTC 2020 up 44 days, 23:20, 0 users, load averages: 1.80, 1.71, 1.72