Trick y way about factorization

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Trick y way about factorization

Postby Goahead52 » Fri Dec 26, 2014 6:15 pm UTC

Here is a new mathematical trick about factorization.

When you have an odd semiprime number n=pq with p and q odd prime and you try the trial division by checking all the odd numbers < int(sqrt(n) you have ONLY one prime number satisfying the solution.
What if you have a way to have more than one.
An example :
n=23*71
You compute the square root of n :
int(sqrt(1633))=40
You have only 23 satisfying the solution.
Now I will show you a trick which will give 6 numbers less than 40 solving your problem of factorization.
Here is the algorithm :
Take n and start multiplying by all the numbers start from 3

4899
6532
8165
9798
11431
13064
14697
16330
17963
19596
21229
22862
24495
26128
27761
29394
31027
32660
34293
35926
37559
39192
40825
42458
44091
45724
47357
48990
50623
52256
53889
55522
57155
58788
60421
62054
63687
65320

Each time you multiply n by k you compute

n*k=m^2+r where m^2 is the biggest square < n*k

Then you compute

first : d=m-r

Second : gcd(d,n)

If gcd(nd,n)>1 you stop because you have one factor.

For n=1633 you have 6 numbers satisfying the solution :

{3,8,16,26,28,39}

Instead of one number 23 you have 6 opportunities to find the solution.

For sure you have more calculation to do.

That is not the problem.
The problem is :
- how the number of solution behave a n get bigger (you need to study the number of solutions compared to int(sqrt(n)))
- how to choose those numbers k (is there any link conducing to direct hit? yes or no)

Once you solve those problems you will see that the factorization is not a hard problem.

How if I publish another method (more efficient than the one I presented here) multiplying the opportunities to find quickly the factor p (assuming that q>p)

I`m really sorry if I tell you that there are many ways on how to afford the factorization and I can not focus on long calculations.
I wish happy new year.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Trick y way about factorization

Postby Forest Goose » Fri Dec 26, 2014 7:34 pm UTC

I don't follow what this has to do with factorization. You aren't factorizing n, what do the six solutions solve? Why do you want six solutions to something else? Could you show me using 15 = 3 * 5 how this would factor it (maybe that would be simpler)?
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

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

Re: Trick y way about factorization

Postby Goahead52 » Fri Dec 26, 2014 7:49 pm UTC

Forest Goose wrote:I don't follow what this has to do with factorization. You aren't factorizing n, what do the six solutions solve? Why do you want six solutions to something else? Could you show me using 15 = 3 * 5 how this would factor it (maybe that would be simpler)?

If you take n=1633
You multiply by 3
1633*3=4899
4899=69^2+138
d=69-138=-69
you take the absolute value 69
gcd(1633,69)=23
so you have one factor.
You can do the same with the 6 values 3,6,8,16,26,28,39 you will have the factors 23 and 71.

Anyway you will always have more than one (which is what you get with trial division)

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

Re: Trick y way about factorization

Postby Goahead52 » Fri Dec 26, 2014 7:53 pm UTC

n=15

15*3=45=6^2+9
d=6-9=-3

gcd(15,3)=3

hence 15=3*5

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Trick y way about factorization

Postby Forest Goose » Sat Dec 27, 2014 4:41 am UTC

I see what you're doing now, I still don't see the point...gcd(n, k) will always give a divisor of n, is there some reason the number manipulation makes it able to arrive at a solution faster than trial division - and does the work in getting there take less time over all, when all is said and done? That you have no proofs, are using semiprimes and gcd instead of just division, and have left, what look like, problems to the reader, make me very inclined to not take you on faith. Can you back any of this up as actually faster, in general?
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

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

Re: Trick y way about factorization

Postby Goahead52 » Sat Dec 27, 2014 11:30 am UTC

I did not say faster or my method is in some way more efficient than trial division.
n=pq p and q odd primes
if 2*p is < int(sqrt(n)) then there is only one factor dividing n between 3 and int(sqrt(n))

If you apply my algo there is more than one opportunity to catch the factor dividing n.
If we want an algo faster than division trial we have to understand why it works first.
Then if we could select a tiny range of values giving the result the solution will come quickly.
I tried values of the size 7-8 digits.
Often there are 4-6 numbers < int(sqrt(n)) solving the factorization.
For some numbers there is no solution between 3 and int(sqrt(n)) WHY?

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

Re: Trick y way about factorization

Postby Goahead52 » Sat Dec 27, 2014 11:37 am UTC

Assume that there k primes between 2 and int(sqrt(n)).
In trial division you have to check the k numbers to find ONLY one factor (in case of odd semiprime).
Imagine a sequence U(n) where n take k values from 1 to k.
Imagine that m values out of k values will allow after computation to find a factor.
If m represent 20% k or more then you will have more chances to find the factor.
Such sequence U(n) do exist or no?
If yes how to build it?
Of course such sequence must be computable in reasonable time unless it will worth zero.

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Trick y way about factorization

Postby Lopsidation » Sat Dec 27, 2014 9:35 pm UTC

You may wish to look at existing factoring algorithms like Pollard's rho. Finding a fast factorization algorithm is a very difficult problem that thousands of people have worked on in the past. You're very unlikely to make progress on it without building on existing work. If you're trying this for your own education/amusement though, then by all means play around and have fun with it!

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

Re: Trick y way about factorization

Postby Goahead52 » Sun Dec 28, 2014 12:22 am UTC

Lopsidation wrote:You may wish to look at existing factoring algorithms like Pollard's rho. Finding a fast factorization algorithm is a very difficult problem that thousands of people have worked on in the past. You're very unlikely to make progress on it without building on existing work. If you're trying this for your own education/amusement though, then by all means play around and have fun with it!

Thank you.
What you are saying is in other words " do not think out of the mainstream otherwise you are an "infidel"".
It reminds me something more religious than scientific.
What I`m trying here is NOT for fun.
I know almost all the factorization algorithm (not deeply for sure) and they are produced around 3 or 4 basic ideas not more.
My permanent problem is the "WHY" the big WHY.
Can you explain me why sometimes it works and someimes it does not work at all.
Zero solution means that something is not working : what?
Many solutions or the number is factorized at the first try means that something is working : what?
I will continue to do it ... for fun.
From funny to serious the distance is often very short.
Anyway thank you very much.

Ps : I`m not mathematician to reassure you.
My knowledge is very basic. I do not say that as excuse.

Parralelex
Posts: 74
Joined: Sun Dec 02, 2012 8:10 am UTC
Location: Location Location

Re: Trick y way about factorization

Postby Parralelex » Sun Dec 28, 2014 2:55 am UTC

So let me see if I understand this.

Step 1: Construct a list of numbers, n*k for k = 1, 2, 3....
Step 2: Calculate the largest number m such that m^2 < n*k
Step 3: Calculate r such that n*k = m^2 + r
Step 4: Calculate d = m - r
Step 5: Calculate gcd(d, n). If it's greater than 1, you have a factor.

Hopefully I have all of that correct.

Let's see what's going on a bit by seeing what d actually is. For a fixed k, d = m - r = m - (n*k - m^2) = m + m^2 - n*k = m(m+1) - n*k.

For you to get a useful gcd out of this, m(m+1) would need to have p or q as a factor, but not both (if it had both as its factors, then the gcd of d and n would be n or some multiple of it). Let's use one of your posts as an example. You factored 1633 using this method, and got 1633*3 = 69^2 + 138. The m in this case is 69. Now, gcd of d and n should give us a solution if 69*70 = 4830 has one of 23 and 71 as a factor, but not both. Well, let's check: 4830 / 23 = 210, but 4830 / 71 = 68.02..., so your method should provide us a factor. And, indeed it does: d = -69, and gcd (69, 1633) = 23.

Some things to note are that you can skip a few steps. Simply taking the highest number m such that m^2 < n*k and taking the gcd of m(m+1) and n would do the exact same thing.

My number theory's fairly rusty, but I don't see any reason why m(m+1) in particular should share a factor with a factor of your n more often than just guessing a number and hoping it's a factor. Maybe I'll think about it some more and try to come up with something. At any rate, thanks for sharing, this is interesting.
I put the "fun" in "mathematics".

And then I took it back out.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Trick y way about factorization

Postby Forest Goose » Sun Dec 28, 2014 4:34 am UTC

One thing to bear in mind is that, as far as I know, doing GCD compared to division picks up a factor of log n (n the number of digits) - that, coupled with the other manipulations, means that is going to take a non-negligible amount of extra work to process a trial - so, even if there are, in general, more viable solutions, it may still take longer, perhaps a decent bit, relatively, to go this route.
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

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

Re: Trick y way about factorization

Postby Goahead52 » Sun Dec 28, 2014 11:15 pm UTC

Parralelex wrote:So let me see if I understand this.

Step 1: Construct a list of numbers, n*k for k = 1, 2, 3....
Step 2: Calculate the largest number m such that m^2 < n*k
Step 3: Calculate r such that n*k = m^2 + r
Step 4: Calculate d = m - r
Step 5: Calculate gcd(d, n). If it's greater than 1, you have a factor.

Hopefully I have all of that correct.

Let's see what's going on a bit by seeing what d actually is. For a fixed k, d = m - r = m - (n*k - m^2) = m + m^2 - n*k = m(m+1) - n*k.

For you to get a useful gcd out of this, m(m+1) would need to have p or q as a factor, but not both (if it had both as its factors, then the gcd of d and n would be n or some multiple of it). Let's use one of your posts as an example. You factored 1633 using this method, and got 1633*3 = 69^2 + 138. The m in this case is 69. Now, gcd of d and n should give us a solution if 69*70 = 4830 has one of 23 and 71 as a factor, but not both. Well, let's check: 4830 / 23 = 210, but 4830 / 71 = 68.02..., so your method should provide us a factor. And, indeed it does: d = -69, and gcd (69, 1633) = 23.

Some things to note are that you can skip a few steps. Simply taking the highest number m such that m^2 < n*k and taking the gcd of m(m+1) and n would do the exact same thing.

My number theory's fairly rusty, but I don't see any reason why m(m+1) in particular should share a factor with a factor of your n more often than just guessing a number and hoping it's a factor. Maybe I'll think about it some more and try to come up with something. At any rate, thanks for sharing, this is interesting.

Right! We could skip some steps and more than that improve the algorithm if we give a particular sequence instead of k=1,2,3,......
But taking ramdomly any number will not give the same result. I have no proof now. Some detailed results will not stand as proof.
Big thanks to you!

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

Re: Trick y way about factorization

Postby Goahead52 » Sun Dec 28, 2014 11:17 pm UTC

Forest Goose wrote:One thing to bear in mind is that, as far as I know, doing GCD compared to division picks up a factor of log n (n the number of digits) - that, coupled with the other manipulations, means that is going to take a non-negligible amount of extra work to process a trial - so, even if there are, in general, more viable solutions, it may still take longer, perhaps a decent bit, relatively, to go this route.

I said it in my post that it implies more calculations than trial division.
Anyway all the algorithm without exception started from an idea an then were improved.
Thank you for your comment.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Trick y way about factorization

Postby Forest Goose » Mon Dec 29, 2014 7:37 am UTC

Goahead52 wrote:I said it in my post that it implies more calculations than trial division.
Anyway all the algorithm without exception started from an idea an then were improved.
Thank you for your comment.


It's not just that it takes more calculations, but that the gcd seems to require a non-negligible amount more - in short, it's something you need to be very aware of when you are calculating how many calculations are used; for example, if you found out that, on average, you could get by with half as many gcd's as trial divisions, overall, it still wouldn't be faster, the gcd is worth more than a single division, or even a constant multiple of division.

It might be nice to have some back story on why you think this is more likely to lead to something efficient, compared to all the other calculations one could do. Where did it come from? Why do you expect it to lead to something? Etc. It's neat, but is there something deeper than you just happened upon it one day?
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests