mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2005-06-03, 03:58   #1
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22×79 Posts
Default Pollard's Algorithm & That of Devaraj-a comparison

Many of you are aware of Pollard's algorithm.To illustrate the algorithm
given in the paper "A Generalisation of Fermat's Theorem" on
www.crorepatibaniye.com/failurefunctions
I will take up the same example i.e.16843009 (given for Pollard's elsewhere
on the net).
This can expressed as 2^24 + 65793.

n 2^n+65793 factors

1 65795 5*13159

2 65797 19*3463

3 65801 29*2269

4 65809 65809

5 65825 5*5*2633

6 65857 11*5987

7 65921 65921

8 66049 257*257

_________

We stop here since we have already arrived at the first factor of
the given number since 2 is a primitive root of 257 and
8 belongs to 2 mod(257).

Prima facie this looks much simpler than Pollard's algorithm.Needless to
say we cannot draw conclusions on the basis of one example; I will
continue the discussion tomorow.
A.K. Devaraj
devarajkandadai is offline   Reply With Quote
Old 2005-06-03, 11:28   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by devarajkandadai
Many of you are aware of Pollard's algorithm.To illustrate the algorithm
given in the paper "A Generalisation of Fermat's Theorem" on
www.crorepatibaniye.com/failurefunctions
I will take up the same example i.e.16843009 (given for Pollard's elsewhere
on the net).
This can expressed as 2^24 + 65793.

n 2^n+65793 factors

1 65795 5*13159

2 65797 19*3463

3 65801 29*2269

4 65809 65809

5 65825 5*5*2633

6 65857 11*5987

7 65921 65921

8 66049 257*257

_________

We stop here since we have already arrived at the first factor of
the given number since 2 is a primitive root of 257 and
8 belongs to 2 mod(257).

Prima facie this looks much simpler than Pollard's algorithm.Needless to
say we cannot draw conclusions on the basis of one example; I will
continue the discussion tomorow.
A.K. Devaraj
I see no algorithm here. I only see some numerology. If you have an
algorithm, please state it.

And your "steps" are certainly far from clear. What relation does the last
number (66049) have with the input?

Please show the steps for (say) 11111111111111111111111111111111123
R.D. Silverman is offline   Reply With Quote
Old 2005-06-03, 12:56   #3
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

5×19×107 Posts
Default

Quote:
Originally Posted by R.D. Silverman
I see no algorithm here. I only see some numerology. If you have an
algorithm, please state it.

And your "steps" are certainly far from clear. What relation does the last
number (66049) have with the input?

Please show the steps for (say) 11111111111111111111111111111111123
The original post clearly stated that the algorithm is given at www.crorepatibaniye.com/failurefunctions
rather than in the post itself.

I'm taking a quick look at it now.


Paul
xilman is offline   Reply With Quote
Old 2005-06-04, 05:28   #4
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

4748 Posts
Default

Quote:
Originally Posted by devarajkandadai
Many of you are aware of Pollard's algorithm.To illustrate the algorithm
given in the paper "A Generalisation of Fermat's Theorem" on
www.crorepatibaniye.com/failurefunctions
I will take up the same example i.e.16843009 (given for Pollard's elsewhere
on the net).
This can expressed as 2^24 + 65793.

n 2^n+65793 factors

1 65795 5*13159

2 65797 19*3463

3 65801 29*2269

4 65809 65809

5 65825 5*5*2633

6 65857 11*5987

7 65921 65921

8 66049 257*257

_________

We stop here since we have already arrived at the first factor of
the given number since 2 is a primitive root of 257 and
8 belongs to 2 mod(257).

Prima facie this looks much simpler than Pollard's algorithm.Needless to
say we cannot draw conclusions on the basis of one example; I will
continue the discussion tomorow.
A.K. Devaraj
To continue:
The last line of the second last para shd read: "16 belongs to 2 (md 257).

In the language of "failure functions" this wd be

n = 8 + 16k is a failure function i.e. if we were to substitute n satisfying this function( where k belongs to N) in 2^n + 65793 we will get
a number exactly divisible by 257. And 2^24 + 65793 , the given number
is exactly divisible by 257.

Pollard's algorithm uses a) gcd, b) random values of a,b,c...and c) arbitrarily
chosen polynomials.

My algorithm uses exponential expressions which are must faster than
polynomials.There is nothing arbi trary about the expression for once the number is given we can express it in an exponential manner as explained in
my paper.Exponential expressions are much faster than polynomials
and as x takes values from 1 to x0, we discover the smallest factor of the
given number gnerally much before x reaches the value x0. I must
admit that my algorithm, although very useful in factorising very large
numbers, is a failure in the case of numbers like F6,F7 and F8 where
very large prime factors are involved.
I therefore suggest that a bechmark test involving 10 randomly chosen very large numbers
be factorised both by rho(n) and a suitable program (like the one suggested by Maxal) be effected.

A.K. Devaraj
devarajkandadai is offline   Reply With Quote
Old 2005-06-04, 13:42   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·3·5·11 Posts
Default

Sorry but I do not see how you can avoid computing gcds as in the Pollard rho algorithm.

It appears that in this example you were lucky, but in general you need about sqrt(p) iterations, where the number p is the prime you find with this algorithm.

Without reducing mod N and computing gcds, the powers of 2 grow without limit making the algorithm unusable. For example, when the prime p to be found is about one trillion or 10^12 (easy to compute with Pollard Rho) your algorithm would be using numbers of size about one million digits if you do not reduce mod N.

Please use another example.

Best regards,

Dario Alpern
alpertron is offline   Reply With Quote
Old 2005-06-05, 06:00   #6
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22·79 Posts
Default

Quote:
Originally Posted by alpertron
Sorry but I do not see how you can avoid computing gcds as in the Pollard rho algorithm.

It appears that in this example you were lucky, but in general you need about sqrt(p) iterations, where the number p is the prime you find with this algorithm.

Without reducing mod N and computing gcds, the powers of 2 grow without limit making the algorithm unusable. For example, when the prime p to be found is about one trillion or 10^12 (easy to compute with Pollard Rho) your algorithm would be using numbers of size about one million digits if you do not reduce mod N.

Please use another example.

Best regards,

Dario Alpern
Fine.Here is an example I used at the DMA Conference held in S.India
in Dec "04.

2^9780675417 + 37

This number has approximately 2.94 billion digits.Yet using onlya 10-digit scientific calculator and this algorithm I could find that 3 & 11 are
factors. Incidentally I give below a list of some of the non-factors as they occur in the
algorithm working till x = 24:



13,41,5, 53,,23, 101, 293, 61,,1061,.........1048613..

You may ask "what is the use of the list of non-factors when we know that
all prime numbers other than factors are non-factors?"

The reasons: a) non-factors include "impossible factors" also .For example
7, 17 & 19 are impossible factors i.e. they cannot be factors of the given
number no matter how large x is.
b) The algorithm reveals the above as non-factors, not in any
probabality sense, but with absolute certainty . Ignoring the aspect of non-factors the question is can Pollard's algorithm handle such huge numbers?

I must, however, reiterate the limitation of my algorithm: it is useless in the
case of numbers having large prime factors.

I may be wrong but I still feel a benchmark test involving randomly chosen
large numbers is desirable.Tks & regards'
A.K. Devaraj
devarajkandadai is offline   Reply With Quote
Old 2005-06-05, 10:42   #7
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

AC116 Posts
Default

Quote:
Originally Posted by devarajkandadai
I must, however, reiterate the limitation of my algorithm: it is useless in the
case of numbers having large prime factors.

A.K. Devaraj
How would you define "large prime factors"?
garo is offline   Reply With Quote
Old 2005-06-05, 13:57   #8
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

5×19×107 Posts
Default

Quote:
Originally Posted by garo
How would you define "large prime factors"?
How fast is your computer?

Trial division and Pollard rho are not very good for finding large factors either. Come to that, neither is ECM or P-1P+1 --- if your idea of "large" is appropriately phrased.


Paul
xilman is offline   Reply With Quote
Old 2005-06-05, 16:52   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I read the PDF. As far as I understood, your idea is sieving values

a^x + c == 0 (mod p)

as by letting x vary.

From the definition of the order of an element of a finite group, we immediately have with o = ord_p (a)

a^(x % o) * a^(k*o) + c = 0 (mod p)
a^(x % o) + c = 0 (mod p)

Clearly the sequence of values as x varies is periodic with period o. By Lagrange's theorem, o|p-1, and the period p-1 is what you discovered. This is, however, not neccessarily the smallest period for given a, p, so your proposed method is not fully generalised yet.

Unfortunately, this method is neither new nor very useful for factoring. The problem of finding an x where the congurnce holds for arbitrary a, c and large p is believed to be very hard - it is the so-called discrete logarithm problem that is one of the fundamental problems used for asymmetric cryptosystems because no efficient algorithm is known to solve it (except in special cases, afaik). For smaller p, the discrete logarithm can be solved, but the idea isn't very useful for factoring... usually you start with a composite number and want to know which factors divide it, not the other way around.

Most of these ideas for potential factoring algorithm are very conveniently explained by finite groups and the order of elements in those. I urge you to study them. If you are only interested in factoring and primality testing, Abelian groups will do - don't bother with permutation groups, normal subgroups etc. which greatly reduces the scope of the subject.

Alex
akruppa is offline   Reply With Quote
Old 2005-06-06, 10:13   #10
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22·79 Posts
Default

Quote:
Originally Posted by garo
How would you define "large prime factors"?
In the context of my algorithm any prime number larger than the exponent
wd be a large prime number. In the example of the 2.94 billion digit given by
me, although the exponent is very small as compared to the number, it is not
a trivial number.
A.K. Devaraj
devarajkandadai is offline   Reply With Quote
Old 2005-06-06, 10:28   #11
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22×79 Posts
Default

Quote:
Originally Posted by akruppa
I read the PDF. As far as I understood, your idea is sieving values

a^x + c == 0 (mod p)

as by letting x vary.

From the definition of the order of an element of a finite group, we immediately have with o = ord_p (a)

a^(x % o) * a^(k*o) + c = 0 (mod p)
a^(x % o) + c = 0 (mod p)

Clearly the sequence of values as x varies is periodic with period o. By Lagrange's theorem, o|p-1, and the period p-1 is what you discovered. This is, however, not neccessarily the smallest period for given a, p, so your proposed method is not fully generalised yet.

Unfortunately, this method is neither new nor very useful for factoring. The problem of finding an x where the congurnce holds for arbitrary a, c and large p is believed to be very hard - it is the so-called discrete logarithm problem that is one of the fundamental problems used for asymmetric cryptosystems because no efficient algorithm is known to solve it (except in special cases, afaik). For smaller p, the discrete logarithm can be solved, but the idea isn't very useful for factoring... usually you start with a composite number and want to know which factors divide it, not the other way around.

Most of these ideas for potential factoring algorithm are very conveniently explained by finite groups and the order of elements in those. I urge you to study them. If you are only interested in factoring and primality testing, Abelian groups will do - don't bother with permutation groups, normal subgroups etc. which greatly reduces the scope of the subject.

Alex
The period In my example is much lesser than (p-1) . 16 is obviously
much lesser than 256. However, this is also a matter of luck.We may get
a case in which the period of the smallest prime factor is (p-1). I must thank you
for your tips on the application of group theory; I will take advantage of them.

The object of the present thread is not the technique for factorising
very large numbers but comparison of the two algorithms in the case of
large but not very large numbers.
A benchmark test of a sufficiently large random sample of numbers should
be taken;the two algorithms be applied ( rho(n) for Pollard's and a suitable programme for mine) and the the time taken noted.
Regards.
A.K. Devaraj
devarajkandadai is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Comparison of NFS tools CRGreathouse Factoring 3 2018-02-05 14:55
Devaraj numbers- necessary and sufficient condition devarajkandadai Number Theory Discussion Group 7 2017-09-23 02:58
Parallelizing Pollard's P-1 Algorithm AnoNYStudent Homework Help 26 2011-12-07 00:18
PFGW vs LLR comparison discussion henryzz Conjectures 'R Us 37 2010-02-19 07:42
Problems with the Pollard Rho Algorithm theta Programming 2 2005-08-26 00:26

All times are UTC. The time now is 22:31.

Fri Aug 7 22:31:27 UTC 2020 up 21 days, 18:18, 1 user, load averages: 2.26, 2.16, 2.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.