mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Alberico Lepore

Reply
 
Thread Tools
Old 2018-01-30, 13:43   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

40310 Posts
Default Semi-prime factorization conjecture

Let N be a semiprimo then

N=a^2-b^2 will have two solutions

a1=(N+1)/2 and b1=(N-1)/2

a2=? b2=? bruteforce on b2 starting from 0

A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1

gcd(A,C)=p_a
gcd(B,D)=p_b
p=(p_a^2-p_b^2)
gcd(A,D)=q_a
gcd(B,C)=q_b
q=(q_b^2-q_a^2)


Example

15=a^2-b^2

a=4 b=1
a=8 b=7

A+B=8 , A-B=4 , C+D=7 , C-D=1
A=6 ,B=2 ,C=4 ,D=3

gcd(A,C)=2
gcd(B,D)=1
p=(2^2-1^2)=3
gcd(A,D)=3
gcd(B,C)=2
q=(3^2-2^2)=5

What do you think about it?
Alberico Lepore is offline   Reply With Quote
Old 2018-01-30, 13:59   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
What do you think about it?
And a3=-4 and b3=1
a4=-8 and b4=7
...
science_man_88 is offline   Reply With Quote
Old 2018-01-30, 14:03   #3
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

13×31 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
And a3=-4 and b3=1
a4=-8 and b4=7
...
They are opposites
Alberico Lepore is offline   Reply With Quote
Old 2018-01-30, 14:53   #4
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

13×31 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post

A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1
A+B=a1 , A-B=a2 , C+D=b1 ,C-D=b2
Alberico Lepore is offline   Reply With Quote
Old 2018-02-03, 01:30   #5
BudgieJane
 
BudgieJane's Avatar
 
"Jane Sullivan"
Jan 2011
Beckenham, UK

23×29 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
Let N be a semiprimo then

What do you think about it?
Do you have an example where N has more than 2 digits. Something like 102 digits would be nice.
BudgieJane is offline   Reply With Quote
Old 2018-02-03, 02:07   #6
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

13·23 Posts
Post

Quote:
Originally Posted by Alberico Lepore View Post
Let N be a semiprimo then

N=a^2-b^2 will have two solutions

a1=(N+1)/2 and b1=(N-1)/2

a2=? b2=? bruteforce on b2 starting from 0

A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1

gcd(A,C)=p_a
gcd(B,D)=p_b
p=(p_a^2-p_b^2)
gcd(A,D)=q_a
gcd(B,C)=q_b
q=(q_b^2-q_a^2)


Example

15=a^2-b^2

a=4 b=1
a=8 b=7

A+B=8 , A-B=4 , C+D=7 , C-D=1
A=6 ,B=2 ,C=4 ,D=3

gcd(A,C)=2
gcd(B,D)=1
p=(2^2-1^2)=3
gcd(A,D)=3
gcd(B,C)=2
q=(3^2-2^2)=5

What do you think about it?
If n is a prime, then the solutions to a^2 = 1 (mod n) are a = +-1 (mod n). If n = p*q where p and q are primes, then the solutions to a^2 = 1 (mod n) are a = +-1, b, and c (mod n) where

b = 1 (mod p) and -1 (mod q)

c = -1 (mod p) and 1 (mod q)

Your "conjecture" follows from this fact.

Last fiddled with by carpetpool on 2018-02-03 at 02:08
carpetpool is offline   Reply With Quote
Old 2018-02-03, 02:41   #7
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

1001010112 Posts
Post

Quote:
Originally Posted by Alberico Lepore View Post
Let N be a semiprimo then

N=a^2-b^2 will have two solutions

a1=(N+1)/2 and b1=(N-1)/2

a2=? b2=? bruteforce on b2 starting from 0

A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1

gcd(A,C)=p_a
gcd(B,D)=p_b
p=(p_a^2-p_b^2)
gcd(A,D)=q_a
gcd(B,C)=q_b
q=(q_b^2-q_a^2)


Example

15=a^2-b^2

a=4 b=1
a=8 b=7

A+B=8 , A-B=4 , C+D=7 , C-D=1
A=6 ,B=2 ,C=4 ,D=3

gcd(A,C)=2
gcd(B,D)=1
p=(2^2-1^2)=3
gcd(A,D)=3
gcd(B,C)=2
q=(3^2-2^2)=5

What do you think about it?
Let's turn this into a game (just for fun).

Here we have semiprimes N = p*q ranging from 90-100 digits. Show that for each one, p = q = 1 (mod n) for a specific n. That is, show each prime dividing N has the form k*n+1.

For example,

N = 5539113502033412895292115974558480983800647735117931750794894952942621260596968647983584706901 (n = 90)

is a semiprime. Show each prime dividing N has the form 90*k+1, or equivalently p = q = 1 (mod 90) where pq = N.

Here are a few more examples (try and show that each prime dividing N has the form k*n+1):

N = 448089051076275785687389418381162972987229036034444427278869256690561568953546204700396224357, (n = 36)

N = 12875011596982825641079225756329235926774793871954944034524736059975902131902515285746205781, (n = 42)

N = 325660878359113486502421634634373166016783555791941517818588883372438081215159258342011023201, (n = 100)

N = 2529326286788100617652188740443724847554819001546212172410115864297421395751726116717093396417, (n = 98)
carpetpool is offline   Reply With Quote
Old 2018-02-16, 08:27   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133478 Posts
Default

Nice game! Could you show us how it works?
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
14° Primality test and factorization of Lepore ( conjecture ) Alberico Lepore Alberico Lepore 48 2017-12-30 09:43
Lepore Factorization in O(k) Conjecture Alberico Lepore Alberico Lepore 61 2017-09-23 21:52
Probability that n is a semi-prime or prime carpetpool Miscellaneous Math 27 2017-01-19 21:00
Prime abc conjecture b == (a-1)/(2^c) miket Miscellaneous Math 6 2013-05-22 05:26
Semi-automated P-1 testing GP2 Marin's Mersenne-aries 2 2003-09-29 19:01

All times are UTC. The time now is 12:08.

Sat Aug 8 12:08:56 UTC 2020 up 22 days, 7:55, 1 user, load averages: 1.25, 1.70, 1.79

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.