My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Reply
 
LinkBack Thread Tools Display Modes
April 21st, 2015, 10:48 AM   #1
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

Primality test and factorization of Lepore-Santo in logarithm

Primality test and factorization of Lepore-Santo in log

forgive translation errors

Factorization and primality test of Lepore-Santo in log [(Y-X) / 6] +1

I will show you the basic example that the factorization of two prime numbers because repeating the process you can factor any number.

Each number NR (not multiple of 2 and 3)divided by six as decimal 1666p and 8333p (p stands for periodic) as per NR module six you will have

1/6= 0,1666p

2 is divisible by 2

3 is divisible by 3

4 is divisible by 2

5/6=0,8333p

6 is divisible by 2 and by 3

and this is equivalent to saying that, starting from 1 you should do once +4 once +2 , and then the set of numbers is not muliplo 2 and 3 will be:

1 1+4=5 5+2=7 7+4=11 11+2=13 13+4=17 17+2=19 19+4=23 23+2=25 25+4=29 29+2=31 ….. ….. ecc.ecc.

then you can see this:

5*5; 25+(1*30) ; 25+(2*30); 25+(3*30); ecc.

5*7; 35+(1*30) ; 35+(2*30); 35+(3*30); ecc.

7*7; 49+(1*42); 49+(2*42); ecc. ecc.

7*11; 77+(1*42); 77+(2*42); ecc. ecc.

From this we derive the three equations:

X^2+n*(X*6)=NR X*(X+2)+n(X*6)=NR X*(X+4)+n(X*6)=NR

where n=(Y-X)/6 in the first equation n=(Y-X-2)/6 in the second equation n=(Y-X-4)/6 in the third equation

So if we find the value of n we find X.

Alberico Lepore 12/04/2015

The idea is to divide by 2, n, until you get to n = 1 (test for n = 1 if the equation transformed from results). If n is even okay, if n is odd we must remove one and divide by two.

How the algorithm works.

Consider 6001=17*357

since 6001/6=1000,1666p and therefore has as a decimal part 1666p we will use the first equation:

X^2+n*(X*6)=6001

and n=56

then

56/2=28

28/2=14

14/2=7 then 7-1=6

6/2=3 then 3-1=2

2/1=1

then the sequence is

par

par

par

odd

odd

So we will modify X^2+n*(X*6)=6001 in to

X^2+n*(X*12)=6001

X^2+n*(X*24)=6001

X^2+n*(X*4=6001

We are in the odd then remove 1 to n which means add X * 48 and divide by 2, and then

X^2+n*(X*96)+48X=6001

yet so odd

X^2+n*(X*192)+96X+48X=6001 then

X^2+n*(X*192)+144X=6001 for n=1

X^2+(X*336)=6001 you will X=17

Now let's see how do I decide whether n is par or is odd

we bring the equation in the form

n*X=(6001 – X^2)/6

The left side equals the right side so if a is par is par to the other also, if it is a odd is odd the other also.

We must consider that X is always odd, then n*X will be par if n is par and will be odd if n is odd.

We see an example of the procedure.

6001/6=1000,166p

(X^2)/6=k,1666 because the squares are always in this form

So we remove 0,1666p to 1000,1666p and we take K,1666p will become k

then we would have 1000-k which is an integer and is to be evaluated if it is par or is odd

we must find the integer values of n

The equation of departure x^2 + n*(6x) = 6001

k is always par because

x^2=(6k+5)^2=36k^2+60k+25 or x^2=(6k+1)^2=36k^2+12k+1

both if you take away one and divide by 6 are par

then

1000-k=par then n par

So the new equation will be x ^ 2 + n * (12x) = 6001

we divide by 2

since k is par. k/2 is an integer then the odd or par value of n will be given only 1000/2 = 500 which is an integer then n is par (as we already knew).

500-k / 2 = integer

see now n / 2 is?

500/2 = 250 we want only the integer values ??of n therefore 250-k/4=integer then 500-k2 = par then that n / 2 is par and then also that k / 2 is par then we did well

see now n / 4 is?

250 / 2 = 125 we want only the integer values ??of n therefore 125-k / 8 = integer, then 250-k/4=par then that n / 4 is par and then also that k / 4 is par then we did well

see now n / 8 is?

125/2=62,5

we want only the integer values of n, hence 62.5-k / 16 = integer, then 125-k / 8 = ODD follows that n / 8 is ODD and therefore also that k / 8 is not an integer then we go wrong because k / 4 was par

we leave unchanged n and integers and take 62. 62-k / 16 = integer then k / 8 = par therefore would be fine for k / 4

62-k / 16 = integer then that 125-k / 8 = odd

Now we can say that n / 8 is odd

Since n / 8 is odd I must subtract 1 and divide by two.

Subtract means subtract 1 to 62

then become 61

see now n / 16 is? 61/2 = 30.5 we want only the integer values of n, hence 30.5-k / 32 = integer, then 61-k/16 = odd so that n / 16 is ODD why this is true? because k/8 is par and n/8 è odd. in the meantime, we have transformed the equation (and at each step we tried for n = 1) that has become

X ^ 2 + n * (X * 192) + 144x = 6001 for n = 1

X ^ 2 + (X * 336) = 6001 you will have X = 17

at this time we are aware of 56

because coming from below and knowing the sequence of odd and par we can get, but we do not care to know

P-P-P-D-D is our sequence

ATTENTION MUST ALWAYS KEEP the K PAR BEFORE THE DIVISION

Alberico Lepore, Ruggiero Santo 15/04/2015

For cases NR / 6 = k, 83333 is a bit different: You multiply the square number to ensure that it becomes a (6 * numeronaturale) +1 that is my k, 16666p, then the new equation will be: Z^2+n*(Z*6)=NR where Z=X^2

Z is proceeding normally, and you to find the square root of X.

The time taken will log{[(Y-X)^2]/6}+1

Alberico Lepore, Ruggiero Santo 20/04/2015

clearly it is here, in Italian Test di primalità e fattorizzazione di Lepore-Santo in log | How to decode RSA

we would like your opinion
gerva is offline  
 
April 21st, 2015, 11:09 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
I'm having trouble following the language. Do you have any code available? that might be easier to understand.
CRGreathouse is offline  
April 21st, 2015, 12:00 PM   #3
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

unfortunately I am not a mathematician and not a computer
gerva is offline  
April 22nd, 2015, 05:24 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by gerva View Post
Consider 6001=17*357

since 6001/6=1000,1666p and therefore has as a decimal part 1666p we will use the first equation:

X^2+n*(X*6)=6001

and n=56
Where do you get n = 56?
CRGreathouse is offline  
April 22nd, 2015, 05:29 AM   #5
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

Quote:
Quote:
Consider 6001=17*357

since 6001/6=1000,1666p and therefore has as a decimal part 1666p we will use the first equation:

X^2+n*(X*6)=6001

and n=56
Where do you get n = 56?
I do not know him.
You will know the end.
but do not need to know.
gerva is offline  
April 22nd, 2015, 05:31 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
So it's not really a factorization method, then, just a certificate of compositeness.
CRGreathouse is offline  
April 22nd, 2015, 05:37 AM   #7
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

He is a primality test and factorization
We are interested to know the sequence of par and odd.

Quote:
Now let's see how do I decide whether n is par or is odd
gerva is offline  
April 22nd, 2015, 07:24 AM   #8
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

Sorry there was an error.
Now is good.

Now let's see how do I decide whether n is par or is odd

we bring the equation in the form

n*X=(6001 – X^2)/6

The left side equals the right side so if a is par is par to the other also, if it is a odd is odd the other also.

We must consider that X is always odd, then n*X will be par if n is par and will be odd if n is odd.

We see an example of the procedure.

6001/6=1000,166p

(X^2)/6=k,1666 because the squares are always in this form

So we remove 0,1666p to 1000,1666p and we take K,1666p will become k

then we would have 1000-k which is an integer and is to be evaluated if it is par or is odd

we must find the integer values of n

The equation of departure x^2 + n*(6x) = 6001

k is always par because

x^2=(6k+5)^2=36k^2+60k+25 or x^2=(6k+1)^2=36k^2+12k+1

both if you take away one and divide by 6 are par

then

1000-k=par then n par

So the new equation will be x ^ 2 + n * (12x) = 6001

we divide by 2

since k is par. k/2 is an integer then the odd or par value of n will be given only 1000/2 = 500 which is an integer then n is par (as we already knew).

500-k / 2 = integer

see now n / 2 is?

500/2 = 250 we want only the integer values of k therefore 250-k/4=integer then 500-k2 = par then that n / 2 is par

see now n / 4 is?

250 / 2 = 125 we want only the integer values of k therefore 125-k / 8 = integer, then 250-k/4=par then that n / 4 is par

see now n / 8 is?

125/2=62,5

we want only the integer values of k, hence 62.5-k / 16 = integer, then 125-k / 8 = ODD follows that n / 8 is ODD

Now we can say that n / 8 is odd

Since n / 8 is odd I must subtract 1 and divide by two.

Subtract means subtract 1 to 62

then become 61

see now n / 16 is?

61/2 = 30.5 we want only the integer values of k, hence 30.5-k / 32 = integer, then 61-k/16 = odd so that n / 16 is ODD

in the meantime, we have transformed the equation (and at each step we tried for n = 1) that has become

X ^ 2 + n * (X * 192) + 144x = 6001 for n = 1

X ^ 2 + (X * 336) = 6001 you will have X = 17

at this time we are aware of 56

because coming from below and knowing the sequence of odd and par we can get, but we do not care to know

P-P-P-D-D is our sequence
gerva is offline  
April 22nd, 2015, 10:43 AM   #9
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

This is correct part ()

Factorization and primality test of Lepore-Santo in log [(Y-X)/6]+1

I will show you the basic example, that i sto say the factorization of two prime numbers because reterating this process we can factor any number.

Each number NR (not multiple of 2 and 3) divided by six gives as decimal 1666p and 8333p (the p is periodic) as for each NR module six we will have

1/6= 0,1666p

2 is divisible by 2

3 is divisible by 3

4 is divisible by 2

5/6=0,8333p

6 is divisible by 2and 3

and this is the same if we start from 1 , doing before +4 and then +2 , so the set of numbers not multiple of 2 and 3 will be:

1
1+4=5
5+2=7
7+4=11
11+2=13
13+4=17
17+2=19
19+4=23
23+2=25
25+4=29
29+2=31
…..
…..
ecc.ecc.

So we can see this:

5*5; 25+(1*30) ; 25+(2*30); 25+(3*30); ecc.
5*7; 35+(1*30) ; 35+(2*30); 35+(3*30); ecc.
7*7; 49+(1*42); 49+(2*42); ecc. ecc.
7*11; 77+(1*42); 77+(2*42); ecc. ecc.

From this we can derive the three equations:

X^2+n*(X*6)=NR
X*(X+2)+n(X*6)=NR
X*(X+4)+n(X*6)=NR

n=(Y-X)/6 in the first equation
n=(Y-X-2)/6 in the second equation
n=(Y-X-4)/6 in the third equation

So if we find the value of n we can get X.

Alberico Lepore 12/04/2015

The idea is to divide by 2 the n until to come at n = 1 (so test for n = 1 if the equation transformed produced results).

If n is even it’s okay, but if n is odd we must remove 1 and divide by two.

How the algorithm works.

Consider 6001=17*357
given that 6001/6=1000,1666p and therefore has as part decimal 1666p we will use the first equation, in fact:

X ^ 2 + n * (X * 6) = 6001

and n = 56

Don’t worry if you don’t understand how I know if n is equal or odd I’ll tell you later.

then

56/2 = 28

2/28 = 14

14/2 = 7 so 7-1 = 6

6/2 = 3 so 3-1 = 2

2/1 = 1

So the sequence is

Even

E

E

Odd

O

Then we can modify X ^ 2 + n * (X * 6) = 6001 to

X ^ 2 + n * (X * 12) = 6001

X ^ 2 + n * (X * 24) = 6001

X ^ 2 + n * (X * 4 = 6001

We are in the odd so remove 1 to n that means adding X*48 more divide by 2:

X^2+n*(X*96)+48X=6001

yet odd so

X^2+n*(X*192)+96X+48X=6001 that better written is

X^2+n*(X*192)+144X=6001 for n = 1

X^2+(X*336)=6001 we will have X = 17

Now let’s see how do to decide if n is even or odd

we bring the equation in the form

n*X=(6001 – X^2)/6

The left part is equal to the right part so if one is equal , is equal also the other ; if one is odd, is odd the other also.

We have to consider that X is always odd then n * X will be even if n is even and will be odd if n is odd.

We see the procedure with an example

6001/6=1000,166p

(X^2)/6=k,1666 because squares are always in this form

So we remove 0,1666p to 1000,1666p and we remove to K, 1666p that will become k

then we would have 1000-k that is an integer and we need to evaluate if it is even or is odd

we have to find the integer values of n.

So the equation x^2 + n*(6x) = 6001

k is always even because

x^2=(6k+5)^2=36k^2+60k+25

or

x^2=(6k+1)^2=36k^2+12k+1

if you take away one and divide by 6 both are equal it follows.

So 1000-k is even and then n is even

So the new equation will be x ^ 2 + n * (12x) = 6001 , we divide by 2

TO BE CONTINUED THIS PART

it is missing here………….

———————————————— ———————————————— ——————————-

other OTHER PART

For the case NR/6=k,83333 is different:

We multiply square number to ensure that it becomes a (6 * natural number) +1 so is my

k,16666p , the new equation will be:

Z^2+n*(Z*6)=NR

Where Z=X^2

so is normally find Z and we do square root to find X.

The time used will be log {[(Y-X) ^ 2] / 6} +1

Alberico Lepore, Ruggiero Santo 22/04/2015

clearly it is here, in Italian Test di primalità e fattorizzazione di Lepore-Santo in log | How to decode RSA
gerva is offline  
April 22nd, 2015, 10:04 PM   #10
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

the missing part is momentarily in Italian. Waiting for translation

Factorization and primality test of Lepore-Santo in log [(Y-X)/6]+1

I will show you the basic example, that i sto say the factorization of two prime numbers because reterating this process we can factor any number.

Each number NR (not multiple of 2 and 3) divided by six gives as decimal 1666p and 8333p (the p is periodic) as for each NR module six we will have

1/6= 0,1666p

2 is divisible by 2

3 is divisible by 3

4 is divisible by 2

5/6=0,8333p

6 is divisible by 2and 3

and this is the same if we start from 1 , doing before +4 and then +2 , so the set of numbers not multiple of 2 and 3 will be:

1
1+4=5
5+2=7
7+4=11
11+2=13
13+4=17
17+2=19
19+4=23
23+2=25
25+4=29
29+2=31
…..
…..
ecc.ecc.

So we can see this:

5*5; 25+(1*30) ; 25+(2*30); 25+(3*30); ecc.
5*7; 35+(1*30) ; 35+(2*30); 35+(3*30); ecc.
7*7; 49+(1*42); 49+(2*42); ecc. ecc.
7*11; 77+(1*42); 77+(2*42); ecc. ecc.

From this we can derive the three equations:

X^2+n*(X*6)=NR
X*(X+2)+n(X*6)=NR
X*(X+4)+n(X*6)=NR

n=(Y-X)/6 in the first equation
n=(Y-X-2)/6 in the second equation
n=(Y-X-4)/6 in the third equation

So if we find the value of n we can get X.

Alberico Lepore 12/04/2015

The idea is to divide by 2 the n until to come at n = 1 (so test for n = 1 if the equation transformed produced results).

If n is even it’s okay, but if n is odd we must remove 1 and divide by two.

How the algorithm works.

Consider 6001=17*357
given that 6001/6=1000,1666p and therefore has as part decimal 1666p we will use the first equation, in fact:

X ^ 2 + n * (X * 6) = 6001

and n = 56

Don’t worry if you don’t understand how I know if n is equal or odd I’ll tell you later.

then

56/2 = 28

2/28 = 14

14/2 = 7 so 7-1 = 6

6/2 = 3 so 3-1 = 2

2/1 = 1

So the sequence is

Even

E

E

Odd

O

Then we can modify X ^ 2 + n * (X * 6) = 6001 to

X ^ 2 + n * (X * 12) = 6001

X ^ 2 + n * (X * 24) = 6001

X ^ 2 + n * (X * 4 = 6001

We are in the odd so remove 1 to n that means adding X*48 more divide by 2:

X^2+n*(X*96)+48X=6001

yet odd so

X^2+n*(X*192)+96X+48X=6001 that better written is

X^2+n*(X*192)+144X=6001 for n = 1

X^2+(X*336)=6001 we will have X = 17

Now let’s see how do to decide if n is even or odd

we bring the equation in the form

n*X=(6001 – X^2)/6

The left part is equal to the right part so if one is equal , is equal also the other ; if one is odd, is odd the other also.

We have to consider that X is always odd then n * X will be even if n is even and will be odd if n is odd.

We see the procedure with an example

6001/6=1000,166p

(X^2)/6=k,1666 because squares are always in this form

So we remove 0,1666p to 1000,1666p and we remove to K, 1666p that will become k

then we would have 1000-k that is an integer and we need to evaluate if it is even or is odd

we have to find the integer values of n.

So the equation x^2 + n*(6x) = 6001

k is always even because

x^2=(6h+5)^2=36h^2+60h+25

or

x^2=(6h+1)^2=36h^2+12h+1

if you take away one and divide by 6 both are equal it follows.

So 1000-k is even and then n is even

So the new equation will be x ^ 2 + n * (12x) = 6001



k/2 è dispari se n=6H+5
k/2 è dispari se n=6H+1
k/2 è dispari n=3F con F dispari

n =1000-k
1000/6=166,6666
166666*6=996
n =1000-k^2=996-[k-4]

996/6=166 e [k-4] è pari quindi non può essere dispari nei primi due casi

vediamo il terzo
1000/3=333,333
n =3*(333)-k=3*(333)-[k-1]
333 è dispari e [(k-1]=DISPARI significa che anche se è diviso 3, F è pari

quindi k/2 è pari
ora possiamo dividiamo per 2
quindi n/2=500 – k/2=pari

velocizzando un po si ha

n/2=498-((k/2)-2)
498/6=83 e ((k/2)-2) è pari quindi non può essere dispari nei primi due casi
(498/3)=166 è pari e ((k/2)-2)=pari significa che anche se è diviso 3, F è pari
k/4=pari
ora possiamo dividiamo per 2
quindi n/4=250 – k/4=pari

n/4=246-[(k/4)-4]
246/6=246 e [(k/4)-4] è pari quindi non può essere dispari nei primi due casi
n/4=249-[(k/4)-1]
(249/3)=83 è dispari e [(k/4)-1] è dispari significa che anche se è diviso 3, F è pari
k/8=pari
ora possiamo dividiamo per 2
quindi n/8=125 – k/8=dispari

siccome è dispari dobbiamo togliere 1 a 125 che diventerà 124

n/8=120-[(k / 8 )-5]
120/6=20 e [(k / 8 )-5] quindi
n/8=(6*20)- [(k / 8 )-5]
siccome k/8 è pari è divisibile per 2
quindi dobbiamo vedere se k/8 è divisibile anche per 3
ma ricordiamo che
k è sempre divisibile per tre perchè
(x^2)-1=(6h+5)^2=36h^2+60h+25-1
oppure
(x^2)-1=(6h+1)^2=36h^2+12h+1
di conseguenza è divisibile per 2 e per tre quindi è divisibile per 6
quindi
n/8=6*(20-G)+5 dove G= k/4

quindi k/16 è dispari
ora possiamo dividiamo per 2
quindi n/16=62 – k/16=dispari

Alberico Lepore, Ruggiero Santo 23/04/2015

———————————————— ———————————————— ———————————————— ——-

for cases NR/6=k,83333 behave similarly

Alberico Lepore, Ruggiero Santo 23/04/2015

Last edited by gerva; April 22nd, 2015 at 10:58 PM.
gerva is offline  
Reply

  My Math Forum > Math Forums > Math

Tags
factorization, lepore, leporesanto, logarithm, primality, santo, test



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality test using combinations Mouhaha Number Theory 6 June 6th, 2017 09:58 AM
Help to disprove a primality test Tylerman Number Theory 4 June 15th, 2012 08:07 PM
Primality test !? mathbalarka Number Theory 1 June 2nd, 2012 03:59 PM
New primality test? Bogauss Number Theory 19 May 24th, 2012 09:26 AM
New primality test momo Number Theory 21 May 2nd, 2009 01:44 PM





Copyright © 2018 My Math Forum. All rights reserved.