Factorization using modular arithmetic
Moderators: gmalivuk, Moderators General, Prelates
Factorization using modular arithmetic
Hi,
Internet is addictive.
Anyway here is a unique method of factorization.
Good bye RSA numbers!
Let us factorize n=1633 using modular arithmetic.
1. We start by picking randomly a number A such as A>int(sqrt(n)) and A<n
A=50
2. We compute A^2=R mod n
50^2=867 mod 1633
R=867
3. We compute B=int(sqrt(R))
B=int(sqrt(867))=29
C=R(B^2)=26
4. We now have :
50^2=(29^2)+26 mod 1633
5. We need to solve X(X+2*29)26=0 mod 1633
X^2+58X=26 mod 1633
If we find X we will then have :
50^2=(X+29)^2 mod 1633
6. It easy to solve it :
X=21
50^2(21+29)^2=0 mod 1633
50+21=71 and 71 divides 1633.
The second solution is X=205
205+29=234
23450=184 GCD(1633,184)=23
234+50=284 GCD(1633,184)=71
Internet is addictive.
Anyway here is a unique method of factorization.
Good bye RSA numbers!
Let us factorize n=1633 using modular arithmetic.
1. We start by picking randomly a number A such as A>int(sqrt(n)) and A<n
A=50
2. We compute A^2=R mod n
50^2=867 mod 1633
R=867
3. We compute B=int(sqrt(R))
B=int(sqrt(867))=29
C=R(B^2)=26
4. We now have :
50^2=(29^2)+26 mod 1633
5. We need to solve X(X+2*29)26=0 mod 1633
X^2+58X=26 mod 1633
If we find X we will then have :
50^2=(X+29)^2 mod 1633
6. It easy to solve it :
X=21
50^2(21+29)^2=0 mod 1633
50+21=71 and 71 divides 1633.
The second solution is X=205
205+29=234
23450=184 GCD(1633,184)=23
234+50=284 GCD(1633,184)=71
 LucasBrown
 Posts: 298
 Joined: Thu Apr 15, 2010 2:57 am UTC
 Location: Poway, CA
Re: Factorization using modular arithmetic
Solving quadratic equations modulo composites is indeed easy when the modulus is small, but when the modulus is large, the best methods we know of involve actually factoring the modulus. So unless you have a fast way to solve modular quadratics that doesn't involve factoring, this isn't going anywhere.
Re: Factorization using modular arithmetic
LucasBrown wrote:Solving quadratic equations modulo composites is indeed easy when the modulus is small, but when the modulus is large, the best methods we know of involve actually factoring the modulus. So unless you have a fast way to solve modular quadratics that doesn't involve factoring, this isn't going anywhere.
Yes I do have an original way to solve quadratic congruence without factoring.
Better than that I have a method to compute phi(pq) where phi() is the Euler totient and p and q odd distinct prime.
I said it before here in this forum.
i`m not programmer and I can not handle large numbers.
But I now I decided to learn programming.
The next year I will come with an algorithm efficient deeply tested.
As gift I will give the factors of the largest RSA challenge (ended challenge unfortunately).
I do not need money anyway.
All the money will go charities.
Re: Factorization using modular arithmetic
Goahead52 wrote:Now I can rest and cut off internet once for all.
No phone no internet no tv
Drinking fucking eating reading and that`s it.
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/
http://decodedarfur.org/
Re: Factorization using modular arithmetic
Here is a way to solve quadratic congruence using very very elementary tools (no Euclidean algorithm, no Euler theorem, no inverse computing etc...).
This method could be coded and improved.
Quadratic congruence
General form :
a*x^2= b mod c (c odd prime)
gcd(a,c)=1
Example :
Solve :
37*x^2=13 mod 53

The first goal of the algorithm is to transform :
a*x^2= b mod c
in the form :
x^2=d mod c

The equation to solve is :
37*x^2=13 mod 53
We need to have the 2 sides divisible by 2 or another number such as we could reach our target :
16*x^2=40 mod 53
16*x^2=40 mod 53
8 divide both sides :
2*x^2=5 mod 53
2*x^2=48 mod 53
2 divide both sides :
x^2=24 mod 53 (The first goal was reached)
The second step is to use the variable changing to obtain the form :
t^2=e^2 mod 53
x=2t
4*t^2=24 mod 53
t^2=6 mod 53
We see that 2*536=100
Hence t^2=100 mod 53=10^2 mod 53
It leads to t=10
as x=2t=2*10=20
Done!
Let us check it : 37*20^2=14800=13 mod 53
This method could be coded and improved.
Quadratic congruence
General form :
a*x^2= b mod c (c odd prime)
gcd(a,c)=1
Example :
Solve :
37*x^2=13 mod 53

The first goal of the algorithm is to transform :
a*x^2= b mod c
in the form :
x^2=d mod c

The equation to solve is :
37*x^2=13 mod 53
We need to have the 2 sides divisible by 2 or another number such as we could reach our target :
16*x^2=40 mod 53
16*x^2=40 mod 53
8 divide both sides :
2*x^2=5 mod 53
2*x^2=48 mod 53
2 divide both sides :
x^2=24 mod 53 (The first goal was reached)
The second step is to use the variable changing to obtain the form :
t^2=e^2 mod 53
x=2t
4*t^2=24 mod 53
t^2=6 mod 53
We see that 2*536=100
Hence t^2=100 mod 53=10^2 mod 53
It leads to t=10
as x=2t=2*10=20
Done!
Let us check it : 37*20^2=14800=13 mod 53
Re: Factorization using modular arithmetic
LucasBrown wrote:Solving quadratic equations modulo composites is indeed easy when the modulus is small, but when the modulus is large, the best methods we know of involve actually factoring the modulus. So unless you have a fast way to solve modular quadratics that doesn't involve factoring, this isn't going anywhere.
Sometimes I feel deeply disappointed by some comments.
Is mathematics field a religion or science?
As long as there is no use of Latex and very sophisticated formulas all packaged in some mainstream theory ("a la mode") you will remain wrongly suspicious.
The hudge question everyone is asking is : how such hard problem could be solved with elementary tools? First answer : it is either impossible either some sort of mathematical scam.
It makes me smile. I knew (he was one of my big friends) a very rich guy who was always badly dressed little bit dirty living in 2 bedds rooms with his wife and his kids.
People who does not know him were always treating him with contempt.
Even when they suddenly learn that the guy in fact is very rich their first comment is " stolen money", "drug money" and so on.
Fro me It is better I leave.
I definitely have nothing to do here.
More than 200 views in less than 2 days and no one went to the core of the problem.
Even if Terence Tao came here using elementary tools but solving the hardest problem in the world you will not even talk to him.
I
 gmalivuk
 GNU Terry Pratchett
 Posts: 26414
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Factorization using modular arithmetic
And yet, you keep coming back.Goahead52 wrote:Fro me It is better I leave.
I definitely have nothing to do here.
Yes, they did.More than 200 views in less than 2 days and no one went to the core of the problem.
The core of the problem is that you continue to claim that you have a simple way of doing something other mathematicians have found to be devilishly complex, and yet you've never once demonstrated that your simple methods are actually effective. But when people question you, your response is (repeatedly) to quit in a petulant huff, rather than ever offering a concrete illustration of your methods working for what you say they can.
We don't care if you can use LaTeX, we just care if you can do the math you say you can do. So far, we have no reason to believe that you can.

 Posts: 436
 Joined: Wed Sep 21, 2011 3:44 am UTC
Re: Factorization using modular arithmetic
Goahead52, you started by assuming the modulus was prime. LucasBrown was talking about the difficulty of solving the problem with large composite moduli.
Re: Factorization using modular arithmetic
arbiteroftruth wrote:Goahead52, you started by assuming the modulus was prime. LucasBrown was talking about the difficulty of solving the problem with large composite moduli.
In my second post I have just copypaste from my documents a method assuming that c is prime.
That`s it.
But my method remain available even if c is composite numbers.
I posted the method using 4 digit number (1633).
Do you want me to post an example with a number of 500 digits to accept my method?
Nowhere in all the examples given by any method uses 500 digit numbers (in all the mathematics literature).
I told you that I`m not programmer. I use Excel which is limited to few digits.
If you understand my method then you could solve any size if you master programming.
2 guys Harry and Hurry we talking :
Harry : I invented a bomb not nuclear able to blow all the planet Earth
Hurry : What? A not nuclear bomb? It is impossible! All we know are atomic bombs with their variants.
Harry : I assure that I use only elementary materials
Hurry : Ok! Give me a proof!
One year later Harry manufactured the bomb.
Harry : I have the proof. I built it!
Hurry : Show me the proof.
One minute after boooooooooooooooooooommmm
Hurry : And now we are in Hell because of you! Did I ask you for a proof?
Harry : oh! Yesssssssss! Now get me out of the Hell!
Good bye! I regret deeply coming back.
Maths become a Religion with Its Priests and Its Church.
I gave you freely the solution of factorizing any number (RSA or bigger).
It is up to you to manufacture it! After that blow up anything you want.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26414
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Factorization using modular arithmetic
Are you sure? I haven't worked through your method, but I've rarely if ever seen a numbertheory proof that assumes something is prime without depending at some point on its primality. Otherwise why state that assumption in the first place?Goahead52 wrote:arbiteroftruth wrote:Goahead52, you started by assuming the modulus was prime. LucasBrown was talking about the difficulty of solving the problem with large composite moduli.
In my second post I have just copypaste from my documents a method assuming that c is prime.
That`s it.
But my method remain available even if c is composite numbers.
Even if it does work, your lazy copypaste of something that is not apparently relevant to the question you were asked does not engender much confidence that you'd engage in this discussion any differently from all your others.
If you'd like, we can go ahead and ban you to prevent such regrettable mistakes in the future.Goahead52 wrote:Good bye! I regret deeply coming back.
 Soupspoon
 You have done something you shouldn't. Or are about to.
 Posts: 3391
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Factorization using modular arithmetic
Every true genius that has eventually been recognised as such has had to prove themselves, one way or another, probably had to deal with the establishment doubting, rejecting or even ridiculing their ideas. But they were proven right (or more right than those that came before), and we now know them for that and admire them. And laugh at their detractors.
There are doubtless ones that never proved themselves, who gave up and were left unheeded, possibly even for their rightful claim to fame to be usurped by another at a later date. They left no visible legacy. They might as well have been wrong and given up.
Do accept that there is no static belief in the old methods, as a whole. There may be individuals who do not shift position, but there is more to the consensus than individuals. That some are not swayed by rightful new thoughts is the price we pay for ensuring that we aren't all swayed by every wrongful thought that any Tom, Dick or Harry came up with that night they drank too much, got stoned and ended up talking nonsense about how the stars are the holes in the sky where the rain comes in, etc...
The challenge is to earn 'belief' by not just wafting back into the aether at the slightest sign of the natural rigor and questioning that has to be expected. To paraphrase the great philsopher: "Do or do not. There is no posting that you have all the answers then go off in a huff when asked to clear up details."
(Also, Excel can do more digits than four. And with just a little improvisation it can do a lot more digits than it can do 'naturally' by dealing with numbers split across two or more cells. But rather than asking for us to master programming (or use our mastery) to solve your problems whilst we are perhaps a little slow on the uptake, with your intuitive understanding of your own method it would be perhaps better to take on the trivial issue of gaining your own programming experience, as promised. Just a suggestion.)
(Ninjaed, but still wanting to make the point. And there's nothing better to confirm a persecution complex than to get an actual persecution, so I do think it's a viable option...)
There are doubtless ones that never proved themselves, who gave up and were left unheeded, possibly even for their rightful claim to fame to be usurped by another at a later date. They left no visible legacy. They might as well have been wrong and given up.
Do accept that there is no static belief in the old methods, as a whole. There may be individuals who do not shift position, but there is more to the consensus than individuals. That some are not swayed by rightful new thoughts is the price we pay for ensuring that we aren't all swayed by every wrongful thought that any Tom, Dick or Harry came up with that night they drank too much, got stoned and ended up talking nonsense about how the stars are the holes in the sky where the rain comes in, etc...
The challenge is to earn 'belief' by not just wafting back into the aether at the slightest sign of the natural rigor and questioning that has to be expected. To paraphrase the great philsopher: "Do or do not. There is no posting that you have all the answers then go off in a huff when asked to clear up details."
(Also, Excel can do more digits than four. And with just a little improvisation it can do a lot more digits than it can do 'naturally' by dealing with numbers split across two or more cells. But rather than asking for us to master programming (or use our mastery) to solve your problems whilst we are perhaps a little slow on the uptake, with your intuitive understanding of your own method it would be perhaps better to take on the trivial issue of gaining your own programming experience, as promised. Just a suggestion.)
(Ninjaed, but still wanting to make the point. And there's nothing better to confirm a persecution complex than to get an actual persecution, so I do think it's a viable option...)
 Eebster the Great
 Posts: 3000
 Joined: Mon Nov 10, 2008 12:58 am UTC
Re: Factorization using modular arithmetic
Soupspoon, Goahead has made posts here before claiming new methods that don't actually do what he claims they do, such as attempting to prove the Riemann hypothesis and Fermat's last theorem. He doesn't really seem to know what he's doing or even what a mathematical identity is. So there is not much reason to give him the benefit of the doubt this time around.
Re: Factorization using modular arithmetic
Do not get me wrong.
I`m not genius.
I have no idea about what genius mean.
I`m maybe too ignorant of mathematics field to be aware of the complexity of factorizing large numbers.
All I know for sure it that the factorization could be solved using elementary tools no matter how hard it seems.
Before asking for banishing me for ever (your moderator has only one dream : banish Goahead52 for ever).
I will finish by a claim you could check :
If you can solve in one or 2 computing hours or in a minute this diophantine equation :
x^2+y=A where A is known and very large (more than 500 digits) and the couple (x,y) is not known
then factorizing any number (large or not) will be a childish game.
Only one solution is needed.
Answer that question by yes or no. Or yes but it will take one day or reasonable time. Or nooooooooooooooooooo it is as difficult as factorizing large numbers.
Now the moderator is free to banish me.
I will never put my feet here.
Thank you and adios.
I`m not genius.
I have no idea about what genius mean.
I`m maybe too ignorant of mathematics field to be aware of the complexity of factorizing large numbers.
All I know for sure it that the factorization could be solved using elementary tools no matter how hard it seems.
Before asking for banishing me for ever (your moderator has only one dream : banish Goahead52 for ever).
I will finish by a claim you could check :
If you can solve in one or 2 computing hours or in a minute this diophantine equation :
x^2+y=A where A is known and very large (more than 500 digits) and the couple (x,y) is not known
then factorizing any number (large or not) will be a childish game.
Only one solution is needed.
Answer that question by yes or no. Or yes but it will take one day or reasonable time. Or nooooooooooooooooooo it is as difficult as factorizing large numbers.
Now the moderator is free to banish me.
I will never put my feet here.
Thank you and adios.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26414
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Factorization using modular arithmetic
If my eternal dream were to ban you, I would have done so ages ago. I'm offering to help you out, since you keep leaving angrily and then coming back and complaining about how terrible that decision was. So if you want, I can make sure you don't commit the same mistake in the future.
No one is saying do it with a 500digit number. We're saying do it with a composite modulus. Do it with a sixdigit number. Do it in a way that shows you actually understand the reasonable challenges others have leveled at your ambitious claims.
But if you can't or won't do that, then leave and don't come back this time, because you won't get a different reception next time if you behave the same way you've been behaving.
No one is saying do it with a 500digit number. We're saying do it with a composite modulus. Do it with a sixdigit number. Do it in a way that shows you actually understand the reasonable challenges others have leveled at your ambitious claims.
But if you can't or won't do that, then leave and don't come back this time, because you won't get a different reception next time if you behave the same way you've been behaving.
Re: Factorization using modular arithmetic
Goahead52 wrote:I will finish by a claim you could check :
If you can solve in one or 2 computing hours or in a minute this diophantine equation :
x^2+y=A where A is known and very large (more than 500 digits) and the couple (x,y) is not known
then factorizing any number (large or not) will be a childish game.
Only one solution is needed.
Answer that question by yes or no. Or yes but it will take one day or reasonable time. Or nooooooooooooooooooo it is as difficult as factorizing large numbers.
Are you looking for something with more restrictions than x = 1, y = A  1?
gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one metame to experience both body's sensory inputs.

 Posts: 154
 Joined: Sun Oct 22, 2006 4:29 am UTC
Re: Factorization using modular arithmetic
Sizik wrote:Are you looking for something with more restrictions than x = 1, y = A  1?
Or x = 0, y = A. Now that we have two solutions, factoring should be easy.
Re: Factorization using modular arithmetic
Or x=a, y=Aa^2 for all a. That didn't seem so hard. RSA numbers, here I come!
Re: Factorization using modular arithmetic
Goahead52 wrote:Here is a way to solve quadratic congruence using very very elementary tools (no Euclidean algorithm, no Euler theorem, no inverse computing etc...).
This method could be coded and improved.
Quadratic congruence
General form :
a*x^2= b mod c (c odd prime)
gcd(a,c)=1
Example :
Solve :
37*x^2=13 mod 53

The first goal of the algorithm is to transform :
a*x^2= b mod c
in the form :
x^2=d mod c

The equation to solve is :
37*x^2=13 mod 53
We need to have the 2 sides divisible by 2 or another number such as we could reach our target :
16*x^2=40 mod 53
16*x^2=40 mod 53
8 divide both sides :
2*x^2=5 mod 53
2*x^2=48 mod 53
2 divide both sides :
x^2=24 mod 53 (The first goal was reached)
This step can be efficiently done using the Euclidean algorithm, and that is fairly elementary, compared to most other things in number theory.
To be fair, I would say exploiting the fact that a prime is in general prime, and thus the coefficients of both sides can be made to be even is a slick trick. Unfortunately I do not see why this could be guaranteed to be efficient. For example, if we start with 3x^2 = 2 mod 1012143527, applying that step would turn it into 1012143524x^2 = 2 mod 1012143527, which gives a huge coefficient. In fact, it is not even clear that such a process will eventually terminate!
Goahead52 wrote:The second step is to use the variable changing to obtain the form :
t^2=e^2 mod 53
x=2t
4*t^2=24 mod 53
t^2=6 mod 53
We see that 2*536=100
Hence t^2=100 mod 53=10^2 mod 53
It leads to t=10
as x=2t=2*10=20
Done!
Let us check it : 37*20^2=14800=13 mod 53
Why do you not just start by "seeing" that 8 * 53  24 = 400 = 20^2, and thus the solution is x = 20? That seems more efficient.
Goahead52 wrote:Do not get me wrong.
I will finish by a claim you could check :
If you can solve in one or 2 computing hours or in a minute this diophantine equation :
x^2+y=A where A is known and very large (more than 500 digits) and the couple (x,y) is not known
then factorizing any number (large or not) will be a childish game.
Only one solution is needed.
Answer that question by yes or no. Or yes but it will take one day or reasonable time. Or nooooooooooooooooooo it is as difficult as factorizing large numbers.
Assuming your claim that solving this efficiently would make factorizing numbers efficient, then yes it is at least as difficult as factorizing large numbers, by definition.

 Posts: 436
 Joined: Wed Sep 21, 2011 3:44 am UTC
Re: Factorization using modular arithmetic
Goahead52 wrote:arbiteroftruth wrote:Goahead52, you started by assuming the modulus was prime. LucasBrown was talking about the difficulty of solving the problem with large composite moduli.
In my second post I have just copypaste from my documents a method assuming that c is prime.
That`s it.
But my method remain available even if c is composite numbers.
I posted the method using 4 digit number (1633).
In your original post you showed how to factorize 1633 assuming you could solve a quadratic mod 1633. That step happens here:
Goahead52 wrote:5. We need to solve X(X+2*29)26=0 mod 1633
X^2+58X=26 mod 1633
If we find X we will then have :
50^2=(X+29)^2 mod 1633
You glossed over the process of actually finding X. When you were challenged on this step, you posted an example which assumed the modulus was prime, but the modulus is supposed to be the number you're trying to factorize in the first place. So what you've really shown is a method of factoring prime numbers.

 Posts: 224
 Joined: Tue Jun 17, 2008 11:04 pm UTC
Re: Factorization using modular arithmetic
Here's a slightly larger number, but one that still should be well within Excel's ability to handle, if indeed you've found something that scales well enough asymptotically to break RSA. It's the product of two primes, and it's a large enough number that if you can successfully apply your method, it should be a little easier for everyone to understand how it would generalize, but small enough that it shouldn't require any special code or software like a 500digit number might.
2656631477
Can you demonstrate your factoring method on this number, without first factoring it by other means?
2656631477
Can you demonstrate your factoring method on this number, without first factoring it by other means?
Re: Factorization using modular arithmetic
Here is the procedure for n= 2656631477
As I do ti using Excel and trying to explain what I have in mind it take me time to avoid keyboard mistakes.
Here are the first steps with quoting my self (for n=1633)
Let us factorize n=1633 using modular arithmetic.
A number with 10 digits was given to me :
n=2656631477
I`m going to quote myself and at the same time I will solve the factorization of n (10 digits number)
1. We start by picking randomly a number A such as A>int(sqrt(n)) and A<n
A=50
I compute int(sqrt(2656631477))=51542
I pick randomly A=499735624 (I did using Excel function randbetween()
2. We compute A^2=R mod n
50^2=867 mod 1633
I need to find R
R=867
(499735624)^2= 316721665 mod 2656631477
R=316721665
3. We compute B=int(sqrt(R))
B=int(sqrt(867))=29
B=int(sqrt(316721665))=17796
C=R(B^2)=26
C=316721665(17796)^2=24049
4. We now have :
50^2=(29^2)+26 mod 1633
(51542)^2=(17796^2)+24049 mod 2656631477
5. We need to solve X(X+2*29)26=0 mod 1633
X^2+58X=26 mod 1633
X^2+2*17796*X24049= 0 mod 2656631477
If we find X we will then have :
50^2=(X+29)^2 mod 1633
(4997356240)^2=(X+17796)^2 mod 2656631477
6. It easy to solve it :
We need to solve :
X^2+35592*X24049= 0 mod 2656631477
How do we proceed to solve it?
By dividing both sides by the same value and changing variables (there will be lot because n is 10 digits)
Let us rewrite the equation so we could reduce it quickly.
X*(X+35592)=24049 mod 2656631477
We do need each time to factorize the right side.
We will work only evenodd.
If the right is odd we compute 265663147724049 otherwise we divide the 2 sides by powers of 2.
X*(X+35592)=24049 mod 2656631477
X*(X+35592)=2656607428 mod 2656631477
(1/4)*X*(X+35592)=(2656607428/4) mod 2656631477
(1/4)*X*(X+35592)=664151857 mod 2656631477
As the process will take me time because I`m not robot I will give only the results simplified
We have to keep in mind that we have to reduce 35592=4*4449 by changing variable when it is possible.
Here it is possible.
X=4*T
T(4T+4*4449))=664151857 mod 2656631477
4T(T+4449)=664151857 mod 2656631477
4T(T+4449)=1992479620 mod 2656631477
T(T+4449)=498119905 mod 2656631477
(1/4)*T*(T+4449)=539627893 mod 2656631477
and so on
You always have to check if the right part is perfect square.
Forcibly by dividing both sides by the same value and "chasing the odd numbers" you will reach the solution by convergence.
I will send what follows as soon as I finish.
What I`m asking to do is to understand the core of my method not to give attention to some of my mistakes (I`m an old guy who has big trouble focusing on one subject.
As I do ti using Excel and trying to explain what I have in mind it take me time to avoid keyboard mistakes.
Here are the first steps with quoting my self (for n=1633)
Let us factorize n=1633 using modular arithmetic.
A number with 10 digits was given to me :
n=2656631477
I`m going to quote myself and at the same time I will solve the factorization of n (10 digits number)
1. We start by picking randomly a number A such as A>int(sqrt(n)) and A<n
A=50
I compute int(sqrt(2656631477))=51542
I pick randomly A=499735624 (I did using Excel function randbetween()
2. We compute A^2=R mod n
50^2=867 mod 1633
I need to find R
R=867
(499735624)^2= 316721665 mod 2656631477
R=316721665
3. We compute B=int(sqrt(R))
B=int(sqrt(867))=29
B=int(sqrt(316721665))=17796
C=R(B^2)=26
C=316721665(17796)^2=24049
4. We now have :
50^2=(29^2)+26 mod 1633
(51542)^2=(17796^2)+24049 mod 2656631477
5. We need to solve X(X+2*29)26=0 mod 1633
X^2+58X=26 mod 1633
X^2+2*17796*X24049= 0 mod 2656631477
If we find X we will then have :
50^2=(X+29)^2 mod 1633
(4997356240)^2=(X+17796)^2 mod 2656631477
6. It easy to solve it :
We need to solve :
X^2+35592*X24049= 0 mod 2656631477
How do we proceed to solve it?
By dividing both sides by the same value and changing variables (there will be lot because n is 10 digits)
Let us rewrite the equation so we could reduce it quickly.
X*(X+35592)=24049 mod 2656631477
We do need each time to factorize the right side.
We will work only evenodd.
If the right is odd we compute 265663147724049 otherwise we divide the 2 sides by powers of 2.
X*(X+35592)=24049 mod 2656631477
X*(X+35592)=2656607428 mod 2656631477
(1/4)*X*(X+35592)=(2656607428/4) mod 2656631477
(1/4)*X*(X+35592)=664151857 mod 2656631477
As the process will take me time because I`m not robot I will give only the results simplified
We have to keep in mind that we have to reduce 35592=4*4449 by changing variable when it is possible.
Here it is possible.
X=4*T
T(4T+4*4449))=664151857 mod 2656631477
4T(T+4449)=664151857 mod 2656631477
4T(T+4449)=1992479620 mod 2656631477
T(T+4449)=498119905 mod 2656631477
(1/4)*T*(T+4449)=539627893 mod 2656631477
and so on
You always have to check if the right part is perfect square.
Forcibly by dividing both sides by the same value and "chasing the odd numbers" you will reach the solution by convergence.
I will send what follows as soon as I finish.
What I`m asking to do is to understand the core of my method not to give attention to some of my mistakes (I`m an old guy who has big trouble focusing on one subject.
Re: Factorization using modular arithmetic
I stopped the case above because it was messy one for me.
An algorithm well designed could do it in less than second.
Here is how I see the factorization using modular arithmetic.
Maybe some of you could build an algorithm to solve this problem
I started with
x=40
x^2=40^2=53 mod 91

I have to find a new value of x other than 40 such as
x^2=53 mod 91
Let us start by dividing both parts by some number (I use powers of 2 because it is easy)
x^2=38 mod 91
(1/2)*x^2=19 mod 91
(1/2)*x^2=72 mod 91
(1/16)=9 mod 91
9 is a perfect square :
(x/4)^2=3^2 mod 91
x/4=3
x=12
144=12*12
144 mod 91 =53 mod 91
Hence 40^212^=28*52
gcd(28,91)=7
gcd(52,91)=13
Factorization of 91 is done.
91=7*13
Now how to prove that such method will forcibly lead to the factorization?
How to choose the first value of x more rigorously?
How to make to make the process lead with certainty to some square residue?
I can not do more.
An algorithm well designed could do it in less than second.
Here is how I see the factorization using modular arithmetic.
Maybe some of you could build an algorithm to solve this problem
I started with
x=40
x^2=40^2=53 mod 91

I have to find a new value of x other than 40 such as
x^2=53 mod 91
Let us start by dividing both parts by some number (I use powers of 2 because it is easy)
x^2=38 mod 91
(1/2)*x^2=19 mod 91
(1/2)*x^2=72 mod 91
(1/16)=9 mod 91
9 is a perfect square :
(x/4)^2=3^2 mod 91
x/4=3
x=12
144=12*12
144 mod 91 =53 mod 91
Hence 40^212^=28*52
gcd(28,91)=7
gcd(52,91)=13
Factorization of 91 is done.
91=7*13
Now how to prove that such method will forcibly lead to the factorization?
How to choose the first value of x more rigorously?
How to make to make the process lead with certainty to some square residue?
I can not do more.

 Posts: 224
 Joined: Tue Jun 17, 2008 11:04 pm UTC
Re: Factorization using modular arithmetic
Goahead52 wrote:Here is the procedure for n= 2656631477
As I do ti using Excel and trying to explain what I have in mind it take me time to avoid keyboard mistakes.
Here are the first steps with quoting my self (for n=1633)
Let us factorize n=1633 using modular arithmetic.
A number with 10 digits was given to me :
n=2656631477
I`m going to quote myself and at the same time I will solve the factorization of n (10 digits number)
(snipped for brevity, to summarize  choose a random integer a, in this case 499735624, and express a^2 as b^2 + c mod N for integers b and c by subtracting out the largest possible square from the result after reducing a^2 mod N)
4. We now have :
50^2=(29^2)+26 mod 1633
(51542)^2=(17796^2)+24049 mod 2656631477
You've made a small mistake here. I believe you mean instead:
(499735624)^2=(17796^2)+24049 mod 2656631477
But yes, with this correction, this is true.
Goahead52 wrote:5. We need to solve X(X+2*29)26=0 mod 1633
X^2+58X=26 mod 1633
X^2+2*17796*X24049= 0 mod 2656631477
If we find X we will then have :
50^2=(X+29)^2 mod 1633
(4997356240)^2=(X+17796)^2 mod 2656631477
Agreed, if we find X such that:
X^2+2*17796*X24049 = 0 mod 2656631477
Then by rearranging, we obtain:
24049 = X^2+2*17796*X = 0 mod 2656631477
And substituting this in to the corrected equation above:
(499735624)^2=(17796^2)+24049 mod 2656631477
(499735624)^2=(17796^2)+(X^2+2*17796*X) mod 2656631477
(499735624)^2=(X+17796)^2 mod 2656631477
(499735624)^2  (X+17796)^2 = 0 mod 2656631477
So we have established a difference of squares, and then by the identity a^2b^2 = (ab)(a+b), we will obtain two factors (ab) and (a+b) of a multiple of N that have a good chance to each have nontrivial factors of N. Indeed, establishing a difference of squares like this is the basis of some modern factorization algorithms, like the quadratic sieve (https://en.wikipedia.org/wiki/Quadratic_sieve) and its generalizations. Okay.
Goahead52 wrote:6. It easy to solve it :
We need to solve :
X^2+35592*X24049= 0 mod 2656631477
How do we proceed to solve it?
By dividing both sides by the same value and changing variables (there will be lot because n is 10 digits)
Let us rewrite the equation so we could reduce it quickly.
X*(X+35592)=24049 mod 2656631477
We do need each time to factorize the right side.
We will work only evenodd.
If the right is odd we compute 265663147724049 otherwise we divide the 2 sides by powers of 2.
X*(X+35592)=24049 mod 2656631477
X*(X+35592)=2656607428 mod 2656631477
(1/4)*X*(X+35592)=(2656607428/4) mod 2656631477
(1/4)*X*(X+35592)=664151857 mod 2656631477
As the process will take me time because I`m not robot I will give only the results simplified
We have to keep in mind that we have to reduce 35592=4*4449 by changing variable when it is possible.
Here it is possible.
X=4*T
T(4T+4*4449))=664151857 mod 2656631477
4T(T+4449)=664151857 mod 2656631477
4T(T+4449)=1992479620 mod 2656631477
T(T+4449)=498119905 mod 2656631477
(1/4)*T*(T+4449)=539627893 mod 2656631477
and so on
You always have to check if the right part is perfect square.
Forcibly by dividing both sides by the same value and "chasing the odd numbers" you will reach the solution by convergence.
I will send what follows as soon as I finish.
What I`m asking to do is to understand the core of my method not to give attention to some of my mistakes (I`m an old guy who has big trouble focusing on one subject.
Okay, as far as I can tell, your method is essentially equivalent to the following. To solve:
X^2+35592*X = 24049 mod 2656631477
* Let 2' denote the multiplicative inverse of 2 mod 2656631477. In particular, 2' = (2656631477+1)/2 = 1328315739.
* Find a value n such that 2'^(2n) * 24049 = c^2 mod 2656631477, for some c, by bruteforce testing n=0, n=1, n=2, ... and testing each time if the RHS is a perfect square.
Then we have:
X^2+35592*X = 24049 mod 2656631477
2'^(2n) * (X^2+35592*X) = 2'^(2n) * 24049 mod 2656631477
2'^(2n) * (X^2+35592*X) = c^2 mod 2656631477
(2'^n * X) + (2'^n * 35592) (2'^n * X) = c^2 mod 2656631477
I'm not sure what you do next...?
But already the brute force approach to expressing the RHS as a perfect square is going to kill the performance of your method. I'm no number theorist, but if your method is guaranteed to terminate at all, it's at best likely to need O(sqrt N) steps to do so in the typical case, which is asymptotically comparable to plain trial division. So this method is not so good, regardless of what you do next.
Goahead52 wrote:I stopped the case above because it was messy one for me.
An algorithm well designed could do it in less than second.
Here is how I see the factorization using modular arithmetic.
Maybe some of you could build an algorithm to solve this problem
I started with
x=40
x^2=40^2=53 mod 91

I have to find a new value of x other than 40 such as
x^2=53 mod 91
Let us start by dividing both parts by some number (I use powers of 2 because it is easy)
x^2=38 mod 91
(1/2)*x^2=19 mod 91
(1/2)*x^2=72 mod 91
(1/16)=9 mod 91
9 is a perfect square :
(x/4)^2=3^2 mod 91
x/4=3
x=12
144=12*12
144 mod 91 =53 mod 91
Hence 40^212^=28*52
gcd(28,91)=7
gcd(52,91)=13
Factorization of 91 is done.
91=7*13
Now how to prove that such method will forcibly lead to the factorization?
How to choose the first value of x more rigorously?
How to make to make the process lead with certainty to some square residue?
I can not do more.
Here you've taken a much more direct approach than your previous method, and gone for trying to directly find a difference of squares, rather than first setting up a more complicated quadratic.
As I understand it, this new approach to factor an odd number N is equivalent to:
* As before, let 2' = (N+1)/2 be the multiplcative inverse of 2, mod N.
* Choose a random number "a".
* Find n such that 2'^(2n) a^2 = c^2 mod N, by incrementally trying n=0,1,2,... until the remainder when 2'^(2n) a^2 is divided by N is a perfect square. If there is no such n  the values loop without ever hitting a perfect square, which is often the case  try again from the start with a new random "a".
* Then by difference of squares, (2'^(n) a  c)(2'^(n) a + c) = 0 mod N, and if this is nontrivial, then you have a factorization of N.
This is basically Fermat's factorization method ( https://en.wikipedia.org/wiki/Fermat%27 ... ion_method ), except that it chooses a weird way to iterate through possible values to square. From playing with it in a python script, it doesn't appear to have any particular advantages over just trying them all sequentially as in Fermat's method. Given that there are ~sqrt(N) perfect squares in a search space of size N, I'd expect this to be O(sqrt(N)), again asymptotically not much better than trial division.
I think the methods you've presented generally *will* work, in that they will factor products of primes. HOWEVER, you're basically using brute force to find the necessary congruence of squares, and you haven't realized how incredibly inefficient this will be as you scale up to larger numbers. None of your ideas are particularly new either  Fermat's method has been known for a long time, and far better and more sophisticated methods have been known for a long time as well.
In fact, a quick and dirty python implementation seems to indicate that the dumbest possible method  trial division  is actually better than your method, at least when implemented naively. A naive implementation of your second method factors 2656631477 in less than a second as you guessed and even factors a larger example 402118292263 usually in a few seconds to a few tens of seconds, but trial division does even better, factoring 2656631477 virtually instantaneously and 402118292263 in a sixth of a second on my computer.
(Also, it's cool how fast computers are, that they can do this so fast even with a crappy algorithm).
Re: Factorization using modular arithmetic
Thank you very much for taking time to analyze my method.
So if I understood your main criticism of my method all depends on how to solve a quadratic congruence.
You said (I`m quoting you :
"Agreed, if we find X such that:
X^2+2*17796*X24049 = 0 mod 2656631477"
if I find a way to solve this equation quickly or by producing a closed formula giving directly the value of X then the factorization will be done.
Yes or no? I want just a quick answer.
I`m not talking about the method I published.
I`m talking about a method of solving quadratic not yet published.
So if I understood your main criticism of my method all depends on how to solve a quadratic congruence.
You said (I`m quoting you :
"Agreed, if we find X such that:
X^2+2*17796*X24049 = 0 mod 2656631477"
if I find a way to solve this equation quickly or by producing a closed formula giving directly the value of X then the factorization will be done.
Yes or no? I want just a quick answer.
I`m not talking about the method I published.
I`m talking about a method of solving quadratic not yet published.
Re: Factorization using modular arithmetic
LucasBrown wrote:Solving quadratic equations modulo composites is indeed easy when the modulus is small, but when the modulus is large, the best methods we know of involve actually factoring the modulus. So unless you have a fast way to solve modular quadratics that doesn't involve factoring, this isn't going anywhere.
So the main hurdle is solving modular quadratics without factoring.
If I show that it is possible then the factorization will be over.
Yes or no?
I will not give as usual an illustration using large numbers (forget about it because I`m not programmer).
I will post an example on how to solve modular quadratics without factoring.
I`m still waiting for your answer.
 Soupspoon
 You have done something you shouldn't. Or are about to.
 Posts: 3391
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Factorization using modular arithmetic
Goahead52 wrote:(forget about it because I`m not programmer)
Can we aid you in becoming a programmer?
Because for someone who knows novel mathematical methods, it should be trivial to overcome this minor hurdle and no longer be held back by this inconvenience.
Re: Factorization using modular arithmetic
Goahead, may I suggest you go take a course in number theory? It sounds like an area you're very interested in, and yet lack formal training on. Luckily it's also an easily accessible field of math, and it may help you formalize your logic, spot errors and hurdles, and get further ahead than where you are.
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."
Not how I say my name
SecondTalon: "Still better looking than Jesus."
Not how I say my name
Re: Factorization using modular arithmetic
Let me tell you that I`m not a young guy.
I have at best 2 years to live.
So do not ask me to learn number theory or programming.
Solving mathematical problems has nothing to do with mathematics knowledge otherwise all the 100 top mathematician would solved it long time ago.
Be sure that the solution of the factorization will come from an unknown guy.
I`m asking questions needing yes or no as answer. Why not answer instead of showing high contempt toward people who do not see the world like you?
Well, good luck to you.
I definitely quit.
You could banish me then.
I have at best 2 years to live.
So do not ask me to learn number theory or programming.
Solving mathematical problems has nothing to do with mathematics knowledge otherwise all the 100 top mathematician would solved it long time ago.
Be sure that the solution of the factorization will come from an unknown guy.
I`m asking questions needing yes or no as answer. Why not answer instead of showing high contempt toward people who do not see the world like you?
Well, good luck to you.
I definitely quit.
You could banish me then.
 Soupspoon
 You have done something you shouldn't. Or are about to.
 Posts: 3391
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Factorization using modular arithmetic
I am not answering your yes/no because it was not addressed to me. My reply (and Zohar's) are intended to further your cause and cabalities if you let us. No contempt intended on kind my part, at the very least.
Srinivasa Ramanujan, as someone you maybe consider yourself akin to, was tragically failed by the various doctors and circumstances of his regretably short life. Things are better now, so perhaps your own estimate is a bit conservative? Even so, I recon we could get you coding within a far shorter time.
Help us help you help us. Or do not. Your call, if you wish to make one.
Srinivasa Ramanujan, as someone you maybe consider yourself akin to, was tragically failed by the various doctors and circumstances of his regretably short life. Things are better now, so perhaps your own estimate is a bit conservative? Even so, I recon we could get you coding within a far shorter time.
Help us help you help us. Or do not. Your call, if you wish to make one.
Re: Factorization using modular arithmetic
There is way to hit directly the target n=x^2y^2 (n=91 for example or any large semiprime).
So choosing smartly the starting value will lead you to the solution.
I have to check everything before posting.
Treating some cases with few digits and using Excel will for sure lead to bad surprises.
Anyway I will post the 5 or 6 cases treated.
So choosing smartly the starting value will lead you to the solution.
I have to check everything before posting.
Treating some cases with few digits and using Excel will for sure lead to bad surprises.
Anyway I will post the 5 or 6 cases treated.

 Posts: 35
 Joined: Wed Sep 24, 2014 5:01 pm UTC
Re: Factorization using modular arithmetic
"Smartly choosing the starting value" is trivially sufficient for factoring any composite number even by trial division, since you just have to "smartly choose" one of the factors itself. The mere fact that it's possible doesn't lead to any constructive method for actually finding that correct choice.

 Posts: 224
 Joined: Tue Jun 17, 2008 11:04 pm UTC
Re: Factorization using modular arithmetic
Goahead52 wrote:Thank you very much for taking time to analyze my method.
So if I understood your main criticism of my method all depends on how to solve a quadratic congruence.
You said (I`m quoting you :
"Agreed, if we find X such that:
X^2+2*17796*X24049 = 0 mod 2656631477"
if I find a way to solve this equation quickly or by producing a closed formula giving directly the value of X then the factorization will be done.
Yes or no? I want just a quick answer.
I`m not talking about the method I published.
I`m talking about a method of solving quadratic not yet published.
Yes, if you can find a way to efficiently solve arbitrary quadratics modulo N for very large arbitrary values of N, then you should be able to turn that into a method for factoring integers. As others have mentioned, it's very likely that whatever method you have will scale far worse than you think it will based on the small examples you're testing it on.
By the way, even just for your own sake in being able to test and play with these ideas, I suspect you're making a mistake in being so reluctant to pick up a programming language. Python is really really easy to learn. I bet you can already get a general sense of how the below code snippets work and how you would modify them to do other things you want to do, just by reading over them.
Code: Select all
#n = 91
n = 611309
#n = 2656631477
#Computes the largest integer <= sqrt(n)
#Copyandpasted from googling online
def isqrt(n):
x = n
y = (x + 1) / 2
while y < x:
x = y
y = (x + n / x) / 2
return x
#Factoring by trial division
for i in range(2,isqrt(n)):
if n % i == 0:
print i
print (n/i)
break
Also Python can do math on integers with as many digits as you want with absolutely no problem, limited only by your computer's resources.
Code: Select all
#Print out every last digit of 2 to the 1000th power, in its full glory
print 2 ** 1000
What if you want to repeatedly divide a value "a" by 2 modulo n, like you've been doing above, and you want to do it a million times and print the results, for values of "n" that are potentially very large? No problem:
Code: Select all
n = <whatever odd value you want here>
#For odd n, (n+1)/2 is the inverse of 2 mod n because (n+1)/2 * 2 = n+1 = 1 mod n
inv2 = (n+1) / 2
a = 3
for i in range(1,1000000):
a = (a * inv2) % n
print a
Honestly, it's not hard. Feel free to use these as a starting point. With just a small investment of effort, you can be much more efficient at testing your own algorithms and ideas than you are now, and if you are going to continue to explore these ideas, the investment should pay for itself pretty quickly. Even within the span of just days if it lets you test or automate some things that would be hard otherwise.
Re: Factorization using modular arithmetic
Thank you very much even if I had no doubt that solving quadratics will lead to the factorization :
"Yes, if you can find a way to efficiently solve arbitrary quadratics modulo N for very large arbitrary values of N, then you should be able to turn that into a method for factoring integers. As others have mentioned, it's very likely that whatever method you have will scale far worse than you think it will based on the small examples you're testing it on."
I just needed confirmation.
About programming my problem is that I have hard time focusing on details and programming needs lot of focusing (an error as tiny as it could be will require you to find it otherwise you are in trouble). I prefer to focus on ideas even if they require some calculations.
I`m going to give some sort of metaphor about factoring :
When you deal with few digits you need only a gun or at most kalashnikov to kill the little monsters but you have to deal with number sized to 1000`s digits you need a nuclear. My idea is that I have to find a way such the monsters kill each other. Then if I succeed to do it the size will not matter. Huge monsters or little monsters killing each other will open me the path to finally reach the big treasure.
Easy to compute x^2=a mod n (where is large odd semiprime)
If we could find WITHOUT TRIALS an y^2=a mod n then the factoring is done!
Is it possible?
I think yes!
I have to show how we should do it otherwise I will be a dreamer a disabled guy trying to climb the Annapurna.
"Yes, if you can find a way to efficiently solve arbitrary quadratics modulo N for very large arbitrary values of N, then you should be able to turn that into a method for factoring integers. As others have mentioned, it's very likely that whatever method you have will scale far worse than you think it will based on the small examples you're testing it on."
I just needed confirmation.
About programming my problem is that I have hard time focusing on details and programming needs lot of focusing (an error as tiny as it could be will require you to find it otherwise you are in trouble). I prefer to focus on ideas even if they require some calculations.
I`m going to give some sort of metaphor about factoring :
When you deal with few digits you need only a gun or at most kalashnikov to kill the little monsters but you have to deal with number sized to 1000`s digits you need a nuclear. My idea is that I have to find a way such the monsters kill each other. Then if I succeed to do it the size will not matter. Huge monsters or little monsters killing each other will open me the path to finally reach the big treasure.
Easy to compute x^2=a mod n (where is large odd semiprime)
If we could find WITHOUT TRIALS an y^2=a mod n then the factoring is done!
Is it possible?
I think yes!
I have to show how we should do it otherwise I will be a dreamer a disabled guy trying to climb the Annapurna.

 Posts: 35
 Joined: Wed Sep 24, 2014 5:01 pm UTC
Re: Factorization using modular arithmetic
If you could find, without trials, an integer D that evenly divides N, then the problem of factoring N is solved even more directly, without having to slow the algorithm down with excess transformations to and from some other form! Is it possible? Sure, you just have to get really, really lucky every single time, as though you're the proprietor of an actualized nondeterministic Turing machine.
Re: Factorization using modular arithmetic
Hi,
There is something new about factorization using modular arithmetic.
The breakthrough is not for today.
What is this strange sequence?
682,6335,6336,6337,6338,6339,6340,6341,6342,6343,6344,6345,6346,6347,6348,6349,6350,6351,6352,6353,6354,6355,6356,6357,6358,6359,6360,6361,6362,6363,6364,6365,6366,6367,6368,6369,6370,6371,6372,6373,6374,6375,6376,6377,6378,6379,6380,6381,6382,6383,6384,6385,6386,6387,6388,6389,6390,6391,6392,6393,6394,6395,6396,6397,6398,6399,6400,6401,6402,6403,6404,6405,6406,6407,6408,6409,6411,6412,6413,6414,6415,6416,6417,6418,7407,7408,7409,7410,7411,7412,7413,7414,7415,7416,7417,7418,7419,7420,7421,7422,7423,7424,7425,7426,7427,7428,7429,7430,7431,7432,7433,7434,7435,7436,7437,7438,7439,7440,7441,7442,7443,7444,7445,7446,7447,7448,7449,7450,7451,7452,7453,7454,7455,7456,7457,7458,7459,7460,7461,7462,7463,7464,7465,7466,7467,7468,7469,7470,7471,7472,7473,7474,7475,7476,7477,7478,7479,7480,7481,7482,7483,7484,7485,7486,7487,7488,7489,7490,7491,7492,7493,7494,7495,7496,7497,7498,7499,7500,7501,7502,7503,7504,7505,7506,7507,7508,7509,7511,7512,7513,7514,7515,7516,7517,7518,7519,7520,7521,
198 elements with 2 main sequences almost consecutive.
Here is the starting point of my discovery (?)
As I was working on how to factor odd semiprime numbers I have found a quick algorithm.
n=481391=641*751
If we apply my algorithm to each one of those numbers it will lead you to the factorization of n=481391
My big problem is that I do not know how to find those numbers for some given n.
For sure there is some hidden link between the strange sequence and the factors of n.
All the 198 elements s(i) have their gcd(s(i),n)=1.
Applying my algorithm will allow me to find quickly the factors.
By varying one parameter I reached a sequence of 749 elements until now.
For one value of this parameter (2 digits) there are 749 elements revealing the factors of n.
I stopped because I`m using Excel with 1000000 rows (I have a little computer not powerful enough).
I will not publish my algorithm now because I do not understand why it works.
My biggest challenge is first to find the subsets (some are almost consecutive numbers).
Second I need to find the most efficient parameter maximizing the cardinal of the required set.
Third : how all this stuff it behave with n larger.
Any thought any question
Thank you.
Just added : with k=80 I have found a sequence containing 6676 elements. So I think that the maximum should be higher than that.
There is something new about factorization using modular arithmetic.
The breakthrough is not for today.
What is this strange sequence?
682,6335,6336,6337,6338,6339,6340,6341,6342,6343,6344,6345,6346,6347,6348,6349,6350,6351,6352,6353,6354,6355,6356,6357,6358,6359,6360,6361,6362,6363,6364,6365,6366,6367,6368,6369,6370,6371,6372,6373,6374,6375,6376,6377,6378,6379,6380,6381,6382,6383,6384,6385,6386,6387,6388,6389,6390,6391,6392,6393,6394,6395,6396,6397,6398,6399,6400,6401,6402,6403,6404,6405,6406,6407,6408,6409,6411,6412,6413,6414,6415,6416,6417,6418,7407,7408,7409,7410,7411,7412,7413,7414,7415,7416,7417,7418,7419,7420,7421,7422,7423,7424,7425,7426,7427,7428,7429,7430,7431,7432,7433,7434,7435,7436,7437,7438,7439,7440,7441,7442,7443,7444,7445,7446,7447,7448,7449,7450,7451,7452,7453,7454,7455,7456,7457,7458,7459,7460,7461,7462,7463,7464,7465,7466,7467,7468,7469,7470,7471,7472,7473,7474,7475,7476,7477,7478,7479,7480,7481,7482,7483,7484,7485,7486,7487,7488,7489,7490,7491,7492,7493,7494,7495,7496,7497,7498,7499,7500,7501,7502,7503,7504,7505,7506,7507,7508,7509,7511,7512,7513,7514,7515,7516,7517,7518,7519,7520,7521,
198 elements with 2 main sequences almost consecutive.
Here is the starting point of my discovery (?)
As I was working on how to factor odd semiprime numbers I have found a quick algorithm.
n=481391=641*751
If we apply my algorithm to each one of those numbers it will lead you to the factorization of n=481391
My big problem is that I do not know how to find those numbers for some given n.
For sure there is some hidden link between the strange sequence and the factors of n.
All the 198 elements s(i) have their gcd(s(i),n)=1.
Applying my algorithm will allow me to find quickly the factors.
By varying one parameter I reached a sequence of 749 elements until now.
For one value of this parameter (2 digits) there are 749 elements revealing the factors of n.
I stopped because I`m using Excel with 1000000 rows (I have a little computer not powerful enough).
I will not publish my algorithm now because I do not understand why it works.
My biggest challenge is first to find the subsets (some are almost consecutive numbers).
Second I need to find the most efficient parameter maximizing the cardinal of the required set.
Third : how all this stuff it behave with n larger.
Any thought any question
Thank you.
Just added : with k=80 I have found a sequence containing 6676 elements. So I think that the maximum should be higher than that.
Last edited by Goahead52 on Fri Oct 21, 2016 12:46 pm UTC, edited 1 time in total.
Re: Factorization using modular arithmetic
Here is the sequence of 749 elements giving each one the factorization of n=481391
Some are giving p=641 others are giving q=751
223,549,620,2040,2041,2042,2043,2044,2045,2046,2047,2048,18516,18517,18518,18519,18520,18521,18522,18523,18524,18525,18526,18527,18528,18529,18530,18531,18532,18533,18534,18535,18536,18537,18538,18539,18540,18541,18542,18543,18544,18545,18546,18547,18548,18549,18550,18551,18552,18553,18554,18555,18556,18557,18558,18559,18560,18561,18562,18563,18564,18565,18566,18567,18568,18569,18570,18571,18572,18573,18574,18575,18576,18577,18578,18579,18580,18581,18582,18583,18584,18585,18586,18587,18588,18590,18591,18592,18593,18594,18595,18596,18597,18598,18599,18600,18601,18602,18603,18604,18605,18606,18607,18608,18609,18610,18611,18612,18613,18614,18615,18616,18617,18618,18619,18620,18621,18622,18623,18624,18625,18626,18627,18628,18629,18630,18631,18632,18633,18634,18635,18636,18637,18638,18639,18640,18641,18642,18643,18644,18645,18646,18647,18648,18649,18650,18651,18652,18653,18654,18655,18656,18657,18658,18659,18660,18661,18662,18663,18664,18665,18666,18667,18668,18669,18670,18671,18672,18673,18674,18675,18676,18677,18678,18679,18680,18681,18682,18683,18684,18685,18686,18687,18688,18689,18690,18691,18692,18693,18694,18695,18696,18697,18698,18699,18700,18701,18702,18703,18704,18705,18706,18707,18708,18709,18710,18711,18712,18713,18714,18715,18716,18717,18718,18719,18720,18721,18722,18723,18724,18725,18726,18727,18728,18729,18730,18731,18732,18733,18734,18735,18736,18737,18738,18739,18740,18741,18742,18743,18744,18745,18746,18747,18748,18749,18750,18751,18752,18753,18754,18755,18756,18757,18758,18759,18760,18761,18762,18763,18764,18765,18766,18767,18768,18769,18770,18771,18772,18773,18774,18776,18777,18778,18779,18780,18781,18782,18783,18784,18785,18786,18787,18788,18789,18790,18791,18792,18793,18794,18795,18796,18797,18798,18799,18800,18801,18802,18803,18804,18805,18806,18807,18808,18809,18810,18811,18812,18813,18814,18815,18816,18817,18818,18819,18820,18821,18822,18823,18824,18825,18826,18827,18828,18829,18830,18831,18832,18833,18834,18835,18836,18837,18838,18839,18840,18841,18842,18843,18844,18845,18846,18847,18848,18849,18850,18851,18852,18853,18854,18855,18856,18857,18858,18859,18860,18861,18862,18863,18864,18865,18866,18867,18868,18869,18870,18871,18872,18873,18874,18875,18876,18877,18878,18879,18880,18881,18882,18883,18884,18885,18886,18887,18888,18889,18890,18891,18892,18893,18894,18895,18896,18897,18898,18899,18900,18901,18902,18903,18904,18905,18906,18907,18908,18909,18910,18911,18912,18913,18914,18915,18916,18917,18918,18919,18920,18921,18922,18923,18924,18925,18926,18927,18928,18929,18930,18931,18932,18933,18934,18935,18936,18937,18938,18939,18940,18941,18942,18943,18944,18945,18946,18947,18948,18949,18950,18951,18952,18953,18954,18955,18956,18957,18958,18959,18960,18961,18962,18963,18964,18965,18966,18967,18968,18969,18970,18971,18972,18973,18974,18975,18976,18977,18978,18979,18980,18981,18982,18983,18984,18985,18986,18987,18988,18989,18990,18991,18992,18993,18994,18995,18996,18997,18998,18999,19000,19001,19002,19003,19004,19005,19006,19007,19008,19009,19010,19011,19012,19013,19014,19015,19016,19017,19018,19019,19020,19021,19022,19023,19024,19025,19026,19027,19028,19029,19030,19031,19032,19033,19034,19035,19036,19037,19038,19039,19040,19041,19042,19043,19044,19045,19046,19047,19048,19049,19050,19051,19052,19053,19054,19055,19056,19057,19058,19059,19060,19061,19062,19063,19064,19065,19066,19067,19068,19069,19070,19071,19072,19073,19074,19075,19076,19077,19078,19079,19080,19081,19082,19083,19084,19085,19086,19087,19088,19089,19090,19091,19092,19093,19094,19095,19096,19097,19098,19099,19100,19101,19102,19103,19104,19105,19106,19107,19108,19109,19110,19111,19112,19113,19114,19115,19116,19117,19118,19119,19120,19121,19122,19123,19124,19125,19126,19127,19128,19129,19130,19131,19132,19133,19134,19135,19136,19137,19138,19139,19140,19141,19142,19143,19144,19145,19146,19147,19148,19149,19150,19151,19152,19153,19154,19155,19156,19157,19158,19159,19160,19161,19162,19163,19164,19165,19166,19167,19168,19169,19170,19171,19172,19173,19174,19175,19176,19177,19178,19179,19180,19181,19182,19183,19184,19185,19186,19187,19188,19189,19190,19191,19192,19193,19194,19195,19196,19197,19198,19199,19200,19201,19202,19203,19204,19205,19206,19207,19208,19209,19210,19211,19212,19213,19214,19215,19216,19217,19218,19219,19220,19221,19222,19223,19224,19225,19226,19227,19228,19229,19231,19232,19233,19234,19235,19236,19237,19238,19239,19240,19241,19242,19243,19244,19245,19246,19247,19248,19249,19250,19251,19252,19253,19254,19255
There are almost consecutive by waves.
Why?
Some are giving p=641 others are giving q=751
223,549,620,2040,2041,2042,2043,2044,2045,2046,2047,2048,18516,18517,18518,18519,18520,18521,18522,18523,18524,18525,18526,18527,18528,18529,18530,18531,18532,18533,18534,18535,18536,18537,18538,18539,18540,18541,18542,18543,18544,18545,18546,18547,18548,18549,18550,18551,18552,18553,18554,18555,18556,18557,18558,18559,18560,18561,18562,18563,18564,18565,18566,18567,18568,18569,18570,18571,18572,18573,18574,18575,18576,18577,18578,18579,18580,18581,18582,18583,18584,18585,18586,18587,18588,18590,18591,18592,18593,18594,18595,18596,18597,18598,18599,18600,18601,18602,18603,18604,18605,18606,18607,18608,18609,18610,18611,18612,18613,18614,18615,18616,18617,18618,18619,18620,18621,18622,18623,18624,18625,18626,18627,18628,18629,18630,18631,18632,18633,18634,18635,18636,18637,18638,18639,18640,18641,18642,18643,18644,18645,18646,18647,18648,18649,18650,18651,18652,18653,18654,18655,18656,18657,18658,18659,18660,18661,18662,18663,18664,18665,18666,18667,18668,18669,18670,18671,18672,18673,18674,18675,18676,18677,18678,18679,18680,18681,18682,18683,18684,18685,18686,18687,18688,18689,18690,18691,18692,18693,18694,18695,18696,18697,18698,18699,18700,18701,18702,18703,18704,18705,18706,18707,18708,18709,18710,18711,18712,18713,18714,18715,18716,18717,18718,18719,18720,18721,18722,18723,18724,18725,18726,18727,18728,18729,18730,18731,18732,18733,18734,18735,18736,18737,18738,18739,18740,18741,18742,18743,18744,18745,18746,18747,18748,18749,18750,18751,18752,18753,18754,18755,18756,18757,18758,18759,18760,18761,18762,18763,18764,18765,18766,18767,18768,18769,18770,18771,18772,18773,18774,18776,18777,18778,18779,18780,18781,18782,18783,18784,18785,18786,18787,18788,18789,18790,18791,18792,18793,18794,18795,18796,18797,18798,18799,18800,18801,18802,18803,18804,18805,18806,18807,18808,18809,18810,18811,18812,18813,18814,18815,18816,18817,18818,18819,18820,18821,18822,18823,18824,18825,18826,18827,18828,18829,18830,18831,18832,18833,18834,18835,18836,18837,18838,18839,18840,18841,18842,18843,18844,18845,18846,18847,18848,18849,18850,18851,18852,18853,18854,18855,18856,18857,18858,18859,18860,18861,18862,18863,18864,18865,18866,18867,18868,18869,18870,18871,18872,18873,18874,18875,18876,18877,18878,18879,18880,18881,18882,18883,18884,18885,18886,18887,18888,18889,18890,18891,18892,18893,18894,18895,18896,18897,18898,18899,18900,18901,18902,18903,18904,18905,18906,18907,18908,18909,18910,18911,18912,18913,18914,18915,18916,18917,18918,18919,18920,18921,18922,18923,18924,18925,18926,18927,18928,18929,18930,18931,18932,18933,18934,18935,18936,18937,18938,18939,18940,18941,18942,18943,18944,18945,18946,18947,18948,18949,18950,18951,18952,18953,18954,18955,18956,18957,18958,18959,18960,18961,18962,18963,18964,18965,18966,18967,18968,18969,18970,18971,18972,18973,18974,18975,18976,18977,18978,18979,18980,18981,18982,18983,18984,18985,18986,18987,18988,18989,18990,18991,18992,18993,18994,18995,18996,18997,18998,18999,19000,19001,19002,19003,19004,19005,19006,19007,19008,19009,19010,19011,19012,19013,19014,19015,19016,19017,19018,19019,19020,19021,19022,19023,19024,19025,19026,19027,19028,19029,19030,19031,19032,19033,19034,19035,19036,19037,19038,19039,19040,19041,19042,19043,19044,19045,19046,19047,19048,19049,19050,19051,19052,19053,19054,19055,19056,19057,19058,19059,19060,19061,19062,19063,19064,19065,19066,19067,19068,19069,19070,19071,19072,19073,19074,19075,19076,19077,19078,19079,19080,19081,19082,19083,19084,19085,19086,19087,19088,19089,19090,19091,19092,19093,19094,19095,19096,19097,19098,19099,19100,19101,19102,19103,19104,19105,19106,19107,19108,19109,19110,19111,19112,19113,19114,19115,19116,19117,19118,19119,19120,19121,19122,19123,19124,19125,19126,19127,19128,19129,19130,19131,19132,19133,19134,19135,19136,19137,19138,19139,19140,19141,19142,19143,19144,19145,19146,19147,19148,19149,19150,19151,19152,19153,19154,19155,19156,19157,19158,19159,19160,19161,19162,19163,19164,19165,19166,19167,19168,19169,19170,19171,19172,19173,19174,19175,19176,19177,19178,19179,19180,19181,19182,19183,19184,19185,19186,19187,19188,19189,19190,19191,19192,19193,19194,19195,19196,19197,19198,19199,19200,19201,19202,19203,19204,19205,19206,19207,19208,19209,19210,19211,19212,19213,19214,19215,19216,19217,19218,19219,19220,19221,19222,19223,19224,19225,19226,19227,19228,19229,19231,19232,19233,19234,19235,19236,19237,19238,19239,19240,19241,19242,19243,19244,19245,19246,19247,19248,19249,19250,19251,19252,19253,19254,19255
There are almost consecutive by waves.
Why?
Re: Factorization using modular arithmetic
I have tested all the values of the parameter k from 2 to 90 for n=91=7*13 it gave me 2 values of k giving the cardinal maximal (50)
Here are the 2 sequences :
k=6
4,11,31,32,33,34,36,37,38,40,41,43,44,45,46,47,48,50,51,53,54,55,57,58,59,60,61,62,64,66,67,68,69,71,72,73,74,75,76,79,80,81,82,83,85,86,87,88,89,90
k=38
3,10,31,32,33,34,36,37,38,40,41,43,44,45,46,47,48,50,51,53,54,55,57,58,59,60,61,62,64,66,67,68,69,71,72,73,74,75,76,79,80,81,82,83,85,86,87,88,89,90
So if you add the 19 numbers > 91 divisible by 7 or 13 you reach 69 numbers out of 89 (I exclude 1 and 91) so 77.5%.
91 is 2 number digits.
What will happen when n odd semiprime will reach 300 digits?
How many are "eligible"? I mean the maximal cardinal of the subset?
Can we find a formula to detect them? I f yes then the factorization is over (one number suffice to have direct hit on the factors)
Can we compute the value of k and the maximum corresponding to k?
Tomorrow I will post my algorithm.
Anyone could then contribute to clarify what I discovered.
Here are the 2 sequences :
k=6
4,11,31,32,33,34,36,37,38,40,41,43,44,45,46,47,48,50,51,53,54,55,57,58,59,60,61,62,64,66,67,68,69,71,72,73,74,75,76,79,80,81,82,83,85,86,87,88,89,90
k=38
3,10,31,32,33,34,36,37,38,40,41,43,44,45,46,47,48,50,51,53,54,55,57,58,59,60,61,62,64,66,67,68,69,71,72,73,74,75,76,79,80,81,82,83,85,86,87,88,89,90
So if you add the 19 numbers > 91 divisible by 7 or 13 you reach 69 numbers out of 89 (I exclude 1 and 91) so 77.5%.
91 is 2 number digits.
What will happen when n odd semiprime will reach 300 digits?
How many are "eligible"? I mean the maximal cardinal of the subset?
Can we find a formula to detect them? I f yes then the factorization is over (one number suffice to have direct hit on the factors)
Can we compute the value of k and the maximum corresponding to k?
Tomorrow I will post my algorithm.
Anyone could then contribute to clarify what I discovered.
Re: Factorization using modular arithmetic
Algo presentation :
n=481391=641*751
We start by one element of the sequence given above
For example :
s(5)=2041
We compute a :
n=a mod s(5)=1756 mod 2041
K is a parameter
k=30 give a sequence of 749 elements
We compute b=k*a=30*1756=52680
We compute c=abs(bs(5))=526802041=50639
Warning for those who want to code this algorithm.
I corrected because sometimes c is negative so it leads to an error in my Excel You take the absolute value of the difference.
At the end we compute
gcd(n,c)=gcd(481391,50639)=641
Check if it is ok :
481391=641*751
Factorization was done.
If you apply my algo to any of the 749 elements listed above {223,549,620,2040,2041,......} you will always find either p=641 or q=751.
As my computer is very slow and as I`m obliged to enter my parameters one by one I reached until now to :
k=32 1147 elements
k=40 1768 elements
k=50 2027 elements.
Someone with a program could give the maximum for n=481391.
My question is :
Does the maximal cardinal of those sequences grew as n get larger or no?
Is the growth slowing or exploding?
Any published results will help me to understand the problem and to find maybe the definitive solution of the factorization.
n=481391=641*751
We start by one element of the sequence given above
For example :
s(5)=2041
We compute a :
n=a mod s(5)=1756 mod 2041
K is a parameter
k=30 give a sequence of 749 elements
We compute b=k*a=30*1756=52680
We compute c=abs(bs(5))=526802041=50639
Warning for those who want to code this algorithm.
I corrected because sometimes c is negative so it leads to an error in my Excel You take the absolute value of the difference.
At the end we compute
gcd(n,c)=gcd(481391,50639)=641
Check if it is ok :
481391=641*751
Factorization was done.
If you apply my algo to any of the 749 elements listed above {223,549,620,2040,2041,......} you will always find either p=641 or q=751.
As my computer is very slow and as I`m obliged to enter my parameters one by one I reached until now to :
k=32 1147 elements
k=40 1768 elements
k=50 2027 elements.
Someone with a program could give the maximum for n=481391.
My question is :
Does the maximal cardinal of those sequences grew as n get larger or no?
Is the growth slowing or exploding?
Any published results will help me to understand the problem and to find maybe the definitive solution of the factorization.
Last edited by Goahead52 on Fri Oct 21, 2016 1:40 pm UTC, edited 1 time in total.
Re: Factorization using modular arithmetic
I have found a sequence of 16065 elements all revealing the factors 641 and 751.
k=128
All the issue is to find those subsets and the k giving the maximal cardinal.
If we could find a formula giving for sure only one number of those sequences with some k then the factorization will be over.
The only value we know is n odd semiprime.
How to find the solution?
I hope one you will find it.
In parallel I discovered a recursive function giving a direct hit.
As the function requires lot of calculations simplifications rewriting and so on to reach a compact formula I have to do this job before posting it.
We start from some chosen value (with some properties) it will lead us directly and quickly to the factors of n (n odd semiprime).
The main issue here is defining the properties of such starting value.
Ps : I think we could solve the problem by direct hit. I need to know if it will work for any value n (large or not) before posting the solution.
If I were a programmer I will solve it quickly by testing it on large range of values. Unfortunately I need to enter the values to wait and so on. It is taking me lot of time.
k=128
All the issue is to find those subsets and the k giving the maximal cardinal.
If we could find a formula giving for sure only one number of those sequences with some k then the factorization will be over.
The only value we know is n odd semiprime.
How to find the solution?
I hope one you will find it.
In parallel I discovered a recursive function giving a direct hit.
As the function requires lot of calculations simplifications rewriting and so on to reach a compact formula I have to do this job before posting it.
We start from some chosen value (with some properties) it will lead us directly and quickly to the factors of n (n odd semiprime).
The main issue here is defining the properties of such starting value.
Ps : I think we could solve the problem by direct hit. I need to know if it will work for any value n (large or not) before posting the solution.
If I were a programmer I will solve it quickly by testing it on large range of values. Unfortunately I need to enter the values to wait and so on. It is taking me lot of time.
Re: Factorization using modular arithmetic
Conclusion : I need to learn programming that is the only solution so I will not be dependent on others results.
It is really sad.
So good luck to you all.
This time I think that I quit once for all.
Comme disent mes compatriotes : on n`est jamais mieux servi que par soimeme.
It is really sad.
So good luck to you all.
This time I think that I quit once for all.
Comme disent mes compatriotes : on n`est jamais mieux servi que par soimeme.
Who is online
Users browsing this forum: No registered users and 11 guests