mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-02-12, 21:54   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

219710 Posts
Default Factoring n via factors of n-1 or n+1

Are there any such algorithms?
Other than occasional hits of FLT primality test, that is.
Thank you in advance

Last fiddled with by a1call on 2018-02-12 at 22:02
a1call is offline   Reply With Quote
Old 2018-02-12, 22:16   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by a1call View Post
Are there any such algorithms?
Other than occasional hits of FLT primality test, that is.
Thank you in advance
Is the list at the bottom of https://en.wikipedia.org/wiki/Euler%...ization_method what you want to avoid ? Checking if n-1 and n+1 use up all primes below sqrtint(n), is probably fruitless even at small levels.

Last fiddled with by science_man_88 on 2018-02-12 at 22:18
science_man_88 is offline   Reply With Quote
Old 2018-02-12, 22:22   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

133 Posts
Default

Very interesting concept, regardless.
But that's not what I had in mind.
Are there any algorithms that use known factors of n-1 or n+1 to find factor candidates of n?
a1call is offline   Reply With Quote
Old 2018-02-12, 22:35   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135338 Posts
Default

Quote:
Originally Posted by a1call View Post
Are there any such algorithms?
Other than occasional hits of FLT primality test, that is.
It doesn't seem likely. I know all the factors of 2^57828929506774569941382167850941401232743376153559817438751 but that doesn't help me find factors of the number just below it.
CRGreathouse is offline   Reply With Quote
Old 2018-02-12, 22:53   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

133 Posts
Default

How about special forms, say subtract a 1 from you example.
a1call is offline   Reply With Quote
Old 2018-02-12, 22:57   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by a1call View Post
How about special forms, say subtract a 1 from you example.
Then we run into above is a power of two and below is twice one less than the previous power of two.
science_man_88 is offline   Reply With Quote
Old 2018-02-13, 02:22   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

133 Posts
Default

FWIW:

Much better and more complete implantations seem possible.
Basic Conceptual Implementation of the fact that most small Fermat-Pseudoprimes have factors which are 1 greater than integer multiples of 1 less than their smallest factor.

Example:
341 = 11 x 31 = (10 + 1) x (3 x 10) +1

https://en.wikipedia.org/wiki/Fermat...Factorizations

Code:
print("\n**** BZS-100-A by Rashid Naimi (a1call) ****");
print("Basic Conceptual Implementation of the fact that most small Fermat-Pseudoprimes have factors which are 1 greater than integer multiples of 1 less than their smallest factor.");
print("Example:\n341 = 11 x 31 = (10 + 1) x (3 x 10) +1");
print("https://en.wikipedia.org/wiki/Fermat_pseudoprime#Factorizations");
allocatemem(19^8);
forstep(e=3,19^4,2,{
n=2^e-1;
if(isprime(n),next(1););\\Skip prime candidates
o=n-1;
  for(i=0,19^1,\\Increase this range for larger Exponents e
    \\print("i ",i);
    fordiv(o, g, \\ Only useful if all prime factors of n-1 are known
    gg=2^i*g+1;\\print("gg ",gg);
    k= lift(Mod(n,gg));
    if((k == 0) && ((gg) != n), 
      print("\n***** 2^",e," - 1 is divisible by:";);
      print("**** ",g+1);
      next(3);
    );
  );
);
      print("\n***** 2^",e," - 1";);
      print("No factor found.");
      \\next(19);
})
Code:
**** BZS-100-A by Rashid Naimi (a1call) ****
Basic Conceptual Implementation of the fact that most small Fermat-Pseudoprimes have factors which are 1 greater than integer multiples of 1 less than their smallest factor.
Example:
341 = 11 x 31 = (10 + 1) x (3 x 10) +1
https://en.wikipedia.org/wiki/Fermat_pseudoprime#Factorizations

***** 2^9 - 1 is divisible by:
**** 7

***** 2^11 - 1 is divisible by:
**** 23

***** 2^15 - 1 is divisible by:
**** 7

***** 2^21 - 1 is divisible by:
**** 7

***** 2^23 - 1 is divisible by:
**** 47

***** 2^25 - 1 is divisible by:
**** 31

***** 2^27 - 1 is divisible by:
**** 7

***** 2^29 - 1 is divisible by:
**** 59

***** 2^33 - 1 is divisible by:
**** 7

***** 2^35 - 1
No factor found.

***** 2^37 - 1 is divisible by:
**** 223

***** 2^39 - 1 is divisible by:
**** 7

***** 2^41 - 1
No factor found.

***** 2^43 - 1
No factor found.

***** 2^45 - 1 is divisible by:
**** 7

***** 2^47 - 1 is divisible by:
**** 283

***** 2^49 - 1 is divisible by:
**** 127

***** 2^51 - 1 is divisible by:
**** 7

***** 2^53 - 1 is divisible by:
**** 1591

***** 2^55 - 1
No factor found.

***** 2^57 - 1 is divisible by:
**** 7

***** 2^59 - 1
No factor found.

***** 2^63 - 1 is divisible by:
**** 7

***** 2^65 - 1 is divisible by:
**** 31

***** 2^67 - 1
No factor found.

***** 2^69 - 1 is divisible by:
**** 7

***** 2^71 - 1
No factor found.

***** 2^73 - 1 is divisible by:
**** 439

***** 2^75 - 1 is divisible by:
**** 7

***** 2^77 - 1
No factor found.

***** 2^79 - 1
No factor found.

***** 2^81 - 1 is divisible by:
**** 7

***** 2^83 - 1 is divisible by:
**** 167

***** 2^85 - 1 is divisible by:
**** 31

***** 2^87 - 1 is divisible by:
**** 7

***** 2^91 - 1 is divisible by:
**** 127

***** 2^93 - 1 is divisible by:
**** 7

***** 2^95 - 1
No factor found.

***** 2^97 - 1
No factor found.

***** 2^99 - 1 is divisible by:
**** 7

***** 2^101 - 1
No factor found.

***** 2^103 - 1
No factor found.

***** 2^105 - 1 is divisible by:
**** 7

***** 2^109 - 1
No factor found.

***** 2^111 - 1 is divisible by:
**** 7

***** 2^113 - 1 is divisible by:
**** 3391

***** 2^115 - 1
No factor found.

***** 2^117 - 1 is divisible by:
**** 7

***** 2^119 - 1
No factor found.

***** 2^121 - 1 is divisible by:
**** 23

***** 2^123 - 1 is divisible by:
**** 7

***** 2^125 - 1 is divisible by:
**** 31

***** 2^129 - 1 is divisible by:
**** 7

***** 2^131 - 1 is divisible by:
**** 263

***** 2^133 - 1 is divisible by:
**** 127

***** 2^135 - 1 is divisible by:
**** 7

***** 2^137 - 1
No factor found.

***** 2^139 - 1
No factor found.

***** 2^141 - 1 is divisible by:
**** 7

***** 2^143 - 1
No factor found.

***** 2^145 - 1 is divisible by:
**** 31

***** 2^147 - 1 is divisible by:
**** 7

***** 2^149 - 1
No factor found.

***** 2^151 - 1
No factor found.

***** 2^153 - 1 is divisible by:
**** 7

***** 2^155 - 1
No factor found.

***** 2^157 - 1
No factor found.

***** 2^159 - 1 is divisible by:
**** 7

***** 2^161 - 1
No factor found.

***** 2^163 - 1
No factor found.

***** 2^165 - 1 is divisible by:
**** 7

***** 2^167 - 1
No factor found.

***** 2^169 - 1 is divisible by:
**** 8191

***** 2^171 - 1 is divisible by:
**** 7

***** 2^173 - 1
No factor found.

***** 2^175 - 1 is divisible by:
**** 127

***** 2^177 - 1 is divisible by:
**** 7

***** 2^179 - 1 is divisible by:
**** 359

***** 2^181 - 1 is divisible by:
**** 5431

***** 2^183 - 1 is divisible by:
**** 7

***** 2^185 - 1 is divisible by:
**** 31

***** 2^187 - 1
No factor found.

***** 2^189 - 1 is divisible by:
**** 7

***** 2^191 - 1 is divisible by:
**** 383

***** 2^193 - 1
No factor found.

***** 2^195 - 1 is divisible by:
**** 7

***** 2^197 - 1
No factor found.

***** 2^199 - 1
No factor found.

***** 2^201 - 1 is divisible by:
**** 7

***** 2^203 - 1
No factor found.

***** 2^205 - 1 is divisible by:
**** 31

***** 2^207 - 1 is divisible by:
**** 7

***** 2^209 - 1
No factor found.

***** 2^211 - 1 is divisible by:
**** 3799

***** 2^213 - 1 is divisible by:
**** 7

***** 2^215 - 1
No factor found.

***** 2^217 - 1 is divisible by:
**** 127

***** 2^219 - 1 is divisible by:
**** 7

***** 2^221 - 1
No factor found.

***** 2^223 - 1
No factor found.

***** 2^225 - 1 is divisible by:
**** 7

***** 2^227 - 1
No factor found.

***** 2^229 - 1
No factor found.

***** 2^231 - 1 is divisible by:
**** 7

***** 2^233 - 1 is divisible by:
**** 1399

***** 2^235 - 1
No factor found.

***** 2^237 - 1 is divisible by:
**** 7

***** 2^239 - 1 is divisible by:
**** 479

***** 2^241 - 1
No factor found.

***** 2^243 - 1 is divisible by:
**** 7

***** 2^245 - 1 is divisible by:
**** 31

***** 2^247 - 1
No factor found.

***** 2^249 - 1 is divisible by:
**** 7

***** 2^251 - 1 is divisible by:
**** 503

***** 2^253 - 1 is divisible by:
**** 271

***** 2^255 - 1 is divisible by:
**** 7

***** 2^257 - 1
No factor found.

***** 2^259 - 1 is divisible by:
**** 127

***** 2^261 - 1 is divisible by:
**** 7
a1call is offline   Reply With Quote
Old 2018-02-13, 02:40   #8
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·83 Posts
Post

Quote:
Originally Posted by CRGreathouse View Post
It doesn't seem likely. I know all the factors of 2^57828929506774569941382167850941401232743376153559817438751 but that doesn't help me find factors of the number just below it.
The exponent, 57828929506774569941382167850941401232743376153559817438751 is prime, so you know that each prime dividing 2^57828929506774569941382167850941401232743376153559817438751-1 is congruent to 1 (mod 57828929506774569941382167850941401232743376153559817438751). That's useful because now you that 2^57828929506774569941382167850941401232743376153559817438751-1 has no prime factors below 5.782892e+58...
carpetpool is offline   Reply With Quote
Old 2018-02-13, 02:49   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by carpetpool View Post
The exponent, 57828929506774569941382167850941401232743376153559817438751 is prime, so you know that each prime dividing 2^57828929506774569941382167850941401232743376153559817438751-1 is congruent to 1 (mod 57828929506774569941382167850941401232743376153559817438751). That's useful because now you that 2^57828929506774569941382167850941401232743376153559817438751-1 has no prime factors below 5.782892e+58...
Mr Greathouse, is refering to the statement about if factoring nearby numbers helps factor n. The problem is, if it was that easily done, it would be in use for mersenne factoring.
science_man_88 is offline   Reply With Quote
Old 2018-02-13, 03:10   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

133 Posts
Default

Again FWIW:

the concept is based on the observation that just about all small Fermat-Pseudoprimes have factors of the form:

n = (x+1)(xy+1) ...
The pattern gets more complex for larger numbers but the basic characteristic is usually still present, But higher orders of some of the prime factors of the smallest factor combine to produce the other factors.

In it's basic form:

n = (x+1)(xy+1) = x2y+x+xy+1 = x(xy+1+y)+1 => x | n-1

Which is the link between the factors of n-1 and the factors of n.

This is a Theoretical concept and the application is still tentative to the caveat that all of the prime factors of n-1 need to be known, This is often not the case with Merssene Pseudoprimes. So it does not have a practical application for factoring Merssene Pseudoprimes.

Last fiddled with by a1call on 2018-02-13 at 03:30
a1call is offline   Reply With Quote
Old 2018-02-13, 03:45   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by a1call View Post
Again FWIW:

the concept is based on the observation that just about all small Fermat-Pseudoprimes have factors of the form:

n = (x+1)(xy+1) ...
The pattern gets more complex for larger numbers but the basic characteristic is usually still present, But higher orders of some of the prime factors of the smallest factor combine to produce the other factors.

In it's basic form:

n = (x+1)(xy+1) = x2y+x+xy+1 = x(xy+1+y)+1 => x | n-1

Which is the link between the factors of n-1 and the factors of n.

This is a Theoretical concept and the application is still tentative to the caveat that all of the prime factors of n-1 need to be known, This is often not the case with Merssene Pseudoprimes. So it does not have a practical application for factoring Merssene Pseudoprimes.
Also can work with the minus 1 side though. (x-1)(xy-1) =x^2(y)-x-xy+1 also has the property x | n-1
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors UberNumberGeek Factoring 51 2017-02-13 20:30
option for finding multiple factors during trial factoring tha Software 24 2014-06-10 23:31
Big factors Jeff Gilchrist Wagstaff PRP Search 10 2013-04-07 11:07
Missing factors at the 'Known Factors' page MatWur-S530113 PrimeNet 11 2009-01-21 19:08
Factoring of composites with near factors - request for data AntonVrba Factoring 3 2006-02-05 06:30

All times are UTC. The time now is 20:34.


Fri Jan 21 20:34:31 UTC 2022 up 182 days, 15:03, 0 users, load averages: 1.29, 1.44, 1.46

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔