Factorization using modular arithmetic

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Factorization using modular arithmetic

Postby Goahead52 » Mon Oct 03, 2016 1:55 pm UTC

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

234-50=184 GCD(1633,184)=23
234+50=284 GCD(1633,184)=71

User avatar
LucasBrown
Posts: 293
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Re: Factorization using modular arithmetic

Postby LucasBrown » Mon Oct 03, 2016 2:04 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Mon Oct 03, 2016 2:30 pm UTC

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.

lorb
Posts: 404
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Factorization using modular arithmetic

Postby lorb » Mon Oct 03, 2016 5:44 pm UTC

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/

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Mon Oct 03, 2016 9:13 pm UTC

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*53-6=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

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Tue Oct 04, 2016 12:02 pm UTC

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

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Factorization using modular arithmetic

Postby gmalivuk » Tue Oct 04, 2016 3:05 pm UTC

Goahead52 wrote:Fro me It is better I leave.
I definitely have nothing to do here.
And yet, you keep coming back.

More than 200 views in less than 2 days and no one went to the core of the problem.
Yes, they did.
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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

arbiteroftruth
Posts: 363
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: Factorization using modular arithmetic

Postby arbiteroftruth » Tue Oct 04, 2016 3:09 pm UTC

Goahead52, you started by assuming the modulus was prime. LucasBrown was talking about the difficulty of solving the problem with large composite moduli.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Tue Oct 04, 2016 4:50 pm UTC

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 copy-paste 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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Factorization using modular arithmetic

Postby gmalivuk » Tue Oct 04, 2016 4:56 pm UTC

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 copy-paste from my documents a method assuming that c is prime.
That`s it.
But my method remain available even if c is composite numbers.
Are you sure? I haven't worked through your method, but I've rarely if ever seen a number-theory proof that assumes something is prime without depending at some point on its primality. Otherwise why state that assumption in the first place?

Even if it does work, your lazy copy-paste 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.

Goahead52 wrote:Good bye! I regret deeply coming back.
If you'd like, we can go ahead and ban you to prevent such regrettable mistakes in the future.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2387
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Factorization using modular arithmetic

Postby Soupspoon » Tue Oct 04, 2016 5:24 pm UTC

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...)

User avatar
Eebster the Great
Posts: 2693
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Factorization using modular arithmetic

Postby Eebster the Great » Tue Oct 04, 2016 5:41 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Tue Oct 04, 2016 6:05 pm UTC

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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Factorization using modular arithmetic

Postby gmalivuk » Tue Oct 04, 2016 6:50 pm UTC

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 500-digit number. We're saying do it with a composite modulus. Do it with a six-digit 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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Sizik
Posts: 1147
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Factorization using modular arithmetic

Postby Sizik » Tue Oct 04, 2016 8:30 pm UTC

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:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

MostlyHarmless
Posts: 145
Joined: Sun Oct 22, 2006 4:29 am UTC

Re: Factorization using modular arithmetic

Postby MostlyHarmless » Tue Oct 04, 2016 9:12 pm UTC

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.

User avatar
Gwydion
Posts: 335
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Factorization using modular arithmetic

Postby Gwydion » Tue Oct 04, 2016 9:31 pm UTC

Or x=a, y=A-a^2 for all a. That didn't seem so hard. RSA numbers, here I come!

dalcde
Posts: 173
Joined: Fri Apr 06, 2012 5:49 am UTC

Re: Factorization using modular arithmetic

Postby dalcde » Tue Oct 04, 2016 10:07 pm UTC

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*53-6=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.

arbiteroftruth
Posts: 363
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: Factorization using modular arithmetic

Postby arbiteroftruth » Tue Oct 04, 2016 10:10 pm UTC

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 copy-paste 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.

lightvector
Posts: 222
Joined: Tue Jun 17, 2008 11:04 pm UTC

Re: Factorization using modular arithmetic

Postby lightvector » Wed Oct 05, 2016 4:45 am UTC

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 500-digit number might.

2656631477

Can you demonstrate your factoring method on this number, without first factoring it by other means?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Thu Oct 06, 2016 9:38 pm UTC

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*X-24049= 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*X-24049= 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 even-odd.
If the right is odd we compute 2656631477-24049 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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Sun Oct 09, 2016 4:43 pm UTC

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^2-12^=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.

lightvector
Posts: 222
Joined: Tue Jun 17, 2008 11:04 pm UTC

Re: Factorization using modular arithmetic

Postby lightvector » Mon Oct 10, 2016 4:09 am UTC

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*X-24049= 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*X-24049 = 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^2-b^2 = (a-b)(a+b), we will obtain two factors (a-b) 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*X-24049= 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 even-odd.
If the right is odd we compute 2656631477-24049 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 brute-force 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^2-12^=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).

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Mon Oct 10, 2016 10:59 am UTC

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*X-24049 = 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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Mon Oct 10, 2016 8:20 pm UTC

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.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2387
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Factorization using modular arithmetic

Postby Soupspoon » Mon Oct 10, 2016 8:29 pm UTC

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.

User avatar
Zohar
COMMANDER PORN
Posts: 7478
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: Denver

Re: Factorization using modular arithmetic

Postby Zohar » Mon Oct 10, 2016 8:32 pm UTC

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

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Mon Oct 10, 2016 8:46 pm UTC

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.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2387
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Factorization using modular arithmetic

Postby Soupspoon » Mon Oct 10, 2016 9:02 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Tue Oct 11, 2016 3:19 pm UTC

There is way to hit directly the target n=x^2-y^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.

curiosityspoon
Posts: 34
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Factorization using modular arithmetic

Postby curiosityspoon » Tue Oct 11, 2016 8:42 pm UTC

"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.

lightvector
Posts: 222
Joined: Tue Jun 17, 2008 11:04 pm UTC

Re: Factorization using modular arithmetic

Postby lightvector » Wed Oct 12, 2016 5:09 am UTC

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*X-24049 = 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)
#Copy-and-pasted 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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Wed Oct 12, 2016 3:15 pm UTC

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.

curiosityspoon
Posts: 34
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Factorization using modular arithmetic

Postby curiosityspoon » Wed Oct 12, 2016 4:21 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Thu Oct 20, 2016 7:58 pm UTC

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.
Last edited by Goahead52 on Fri Oct 21, 2016 12:46 pm UTC, edited 1 time in total.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Thu Oct 20, 2016 8:11 pm UTC

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?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Thu Oct 20, 2016 11:20 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Fri Oct 21, 2016 9:43 am UTC

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(b-s(5))=52680-2041=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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Fri Oct 21, 2016 1:14 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorization using modular arithmetic

Postby Goahead52 » Fri Oct 21, 2016 10:28 pm UTC

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 soi-meme.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests