|
Science Forum Index » Cryptography Forum » power detection?
Page 1 of 2 Goto page 1, 2 Next
|
| Author |
Message |
| Tom St Denis |
 Posted: Sat Jan 03, 2004 6:23 pm |
|
|
|
Guest
|
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power? Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n)) but
that could get slow...
Thanks,
Tom |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Sat Jan 03, 2004 7:54 pm |
|
|
|
Guest
|
"Michael Scott" <mscott@indigo.ie> wrote in message
news:ysJJb.3107$HR.6829@news.indigo.ie...
Quote:
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n))
but
that could get slow...
Actually its very fast. But Daniel Bernstein has a paper on it
http://citeseer.nj.nec.com/bernstein98detecting.html
I've actually read that paper. Can't say I like Daniels writing style [the
dudes a genius just not good at writing papers]. Are you sure that paper is
for integers and not just floating point types? Maybe I've misread it...
Tom |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Sat Jan 03, 2004 7:54 pm |
|
|
|
Guest
|
"Michael Scott" <mscott@indigo.ie> wrote in message
news:ysJJb.3107$HR.6829@news.indigo.ie...
Quote:
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n))
but
that could get slow...
Actually its very fast. But Daniel Bernstein has a paper on it
http://citeseer.nj.nec.com/bernstein98detecting.html
I've actually read that paper. Can't say I like Daniels writing style [the
dudes a genius just not good at writing papers]. Are you sure that paper is
for integers and not just floating point types? Maybe I've misread it...
Tom |
|
|
| Back to top |
|
| Michael Scott |
| Posted: Sat Jan 03, 2004 7:55 pm |
|
|
|
Guest
|
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
Quote: I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n)) but
that could get slow...
Actually its very fast. But Daniel Bernstein has a paper on it
http://citeseer.nj.nec.com/bernstein98detecting.html
Mike Scott
|
|
|
| Back to top |
|
| Michael Scott |
| Posted: Sat Jan 03, 2004 8:03 pm |
|
|
|
Guest
|
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:7vJJb.119015$INs.97912@twister01.bloor.is.net.cable.rogers.com...
Quote:
"Michael Scott" <mscott@indigo.ie> wrote in message
news:ysJJb.3107$HR.6829@news.indigo.ie...
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n))
but
that could get slow...
Actually its very fast. But Daniel Bernstein has a paper on it
http://citeseer.nj.nec.com/bernstein98detecting.html
I've actually read that paper. Can't say I like Daniels writing style
[the
dudes a genius just not good at writing papers]. Are you sure that paper
is
for integers and not just floating point types? Maybe I've misread it...
Well the abstract says... "given an integer n>1, either writes n as a
perfect power or proves that n is not a perfect power"
Mike
|
|
|
| Back to top |
|
| Michael Scott |
| Posted: Sat Jan 03, 2004 8:03 pm |
|
|
|
Guest
|
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:7vJJb.119015$INs.97912@twister01.bloor.is.net.cable.rogers.com...
Quote:
"Michael Scott" <mscott@indigo.ie> wrote in message
news:ysJJb.3107$HR.6829@news.indigo.ie...
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n))
but
that could get slow...
Actually its very fast. But Daniel Bernstein has a paper on it
http://citeseer.nj.nec.com/bernstein98detecting.html
I've actually read that paper. Can't say I like Daniels writing style
[the
dudes a genius just not good at writing papers]. Are you sure that paper
is
for integers and not just floating point types? Maybe I've misread it...
Well the abstract says... "given an integer n>1, either writes n as a
perfect power or proves that n is not a perfect power"
Mike
|
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Sat Jan 03, 2004 8:21 pm |
|
|
|
Guest
|
"Michael Scott" <mscott@indigo.ie> wrote in message
news:bAJJb.3108$HR.7076@news.indigo.ie...
Quote:
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:7vJJb.119015$INs.97912@twister01.bloor.is.net.cable.rogers.com...
"Michael Scott" <mscott@indigo.ie> wrote in message
news:ysJJb.3107$HR.6829@news.indigo.ie...
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to
log_2(n))
but
that could get slow...
Actually its very fast. But Daniel Bernstein has a paper on it
http://citeseer.nj.nec.com/bernstein98detecting.html
I've actually read that paper. Can't say I like Daniels writing style
[the
dudes a genius just not good at writing papers]. Are you sure that
paper
is
for integers and not just floating point types? Maybe I've misread
it...
Well the abstract says... "given an integer n>1, either writes n as a
perfect power or proves that n is not a perfect power"
It mentions floats alot in the paper. It also says later [section 3] find
pow_{b+something}(x, k)
or something like that. This led me to think it uses large floats to solve
the problem.
Let me rephrase the question. Using only integer arithmetic [e.g. stuff
you'd find in a bignum lib like that of LTM or OpenSSL, etc...].
Tom |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Sat Jan 03, 2004 8:21 pm |
|
|
|
Guest
|
"Michael Scott" <mscott@indigo.ie> wrote in message
news:bAJJb.3108$HR.7076@news.indigo.ie...
Quote:
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:7vJJb.119015$INs.97912@twister01.bloor.is.net.cable.rogers.com...
"Michael Scott" <mscott@indigo.ie> wrote in message
news:ysJJb.3107$HR.6829@news.indigo.ie...
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to
log_2(n))
but
that could get slow...
Actually its very fast. But Daniel Bernstein has a paper on it
http://citeseer.nj.nec.com/bernstein98detecting.html
I've actually read that paper. Can't say I like Daniels writing style
[the
dudes a genius just not good at writing papers]. Are you sure that
paper
is
for integers and not just floating point types? Maybe I've misread
it...
Well the abstract says... "given an integer n>1, either writes n as a
perfect power or proves that n is not a perfect power"
It mentions floats alot in the paper. It also says later [section 3] find
pow_{b+something}(x, k)
or something like that. This led me to think it uses large floats to solve
the problem.
Let me rephrase the question. Using only integer arithmetic [e.g. stuff
you'd find in a bignum lib like that of LTM or OpenSSL, etc...].
Tom |
|
|
| Back to top |
|
| Marcel Martin |
| Posted: Sat Jan 03, 2004 9:31 pm |
|
|
|
Guest
|
Michael Scott a écrit :
Quote:
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n)) but
that could get slow...
Actually its very fast.
Indeed. One has to use not all the values but only the primes in the
range [2..log2(n)].
mm
--
http://www.ellipsa.net/
mm@ellipsa.no.sp.am.net ( suppress no.sp.am. ) |
|
|
| Back to top |
|
| Marcel Martin |
| Posted: Sat Jan 03, 2004 9:31 pm |
|
|
|
Guest
|
Michael Scott a écrit :
Quote:
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n)) but
that could get slow...
Actually its very fast.
Indeed. One has to use not all the values but only the primes in the
range [2..log2(n)].
mm
--
http://www.ellipsa.net/
mm@ellipsa.no.sp.am.net ( suppress no.sp.am. ) |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Sat Jan 03, 2004 9:44 pm |
|
|
|
Guest
|
"Marcel Martin" <mm@ellipsa.no.sp.am.net> wrote in message
news:3FF77AF9.CF8B8E34@ellipsa.no.sp.am.net...
Quote: Michael Scott a écrit :
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n))
but
that could get slow...
Actually its very fast.
Indeed. One has to use not all the values but only the primes in the
range [2..log2(n)].
True that. I was being a tad overly simple.
Problem is root finding is O(n^3) time and there are log2(n)/ln(log2(n))
prime exponents to test. So for n ~ 2^1024 there are 148 primes to test....
Even with a decently optimized root finder [the one in LTM could be written
slightly better] it's still going to take a while.
I think for now I'll implement it the "hard way" and later on change it up
when I find a better way.
Tom |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Sat Jan 03, 2004 9:44 pm |
|
|
|
Guest
|
"Marcel Martin" <mm@ellipsa.no.sp.am.net> wrote in message
news:3FF77AF9.CF8B8E34@ellipsa.no.sp.am.net...
Quote: Michael Scott a écrit :
"Tom St Denis" <tomstdenis@iahu.ca> wrote in message
news:aaIJb.117164$INs.113473@twister01.bloor.is.net.cable.rogers.com...
I tried some citeseering but couldn't find anything..
Any references on detecting whether an integer is a prime power?
Obviously
there is the brute force solution (e.g. try roots from 2 to log_2(n))
but
that could get slow...
Actually its very fast.
Indeed. One has to use not all the values but only the primes in the
range [2..log2(n)].
True that. I was being a tad overly simple.
Problem is root finding is O(n^3) time and there are log2(n)/ln(log2(n))
prime exponents to test. So for n ~ 2^1024 there are 148 primes to test....
Even with a decently optimized root finder [the one in LTM could be written
slightly better] it's still going to take a while.
I think for now I'll implement it the "hard way" and later on change it up
when I find a better way.
Tom |
|
|
| Back to top |
|
| Paul Rubin |
| Posted: Sat Jan 03, 2004 10:18 pm |
|
|
|
Guest
|
"Tom St Denis" <tomstdenis@iahu.ca> writes:
Quote: Problem is root finding is O(n^3) time and there are log2(n)/ln(log2(n))
prime exponents to test. So for n ~ 2^1024 there are 148 primes to test....
Even with a decently optimized root finder [the one in LTM could be written
slightly better] it's still going to take a while.
Unless I miss something, you need to test bases, not exponents.
What's to optimize? If you have some 1024 bit N and you want to know
if it's a power of 137, just compute y=ln(N)/ln(137) with floating
point arithmetic, and if y is near enough to being an integer, check
whether 137**round_to_nearest_int(y)==N. If y isn't very close to
an integer, you don't even need to bother with the exact integer test. |
|
|
| Back to top |
|
| Paul Rubin |
| Posted: Sat Jan 03, 2004 10:18 pm |
|
|
|
Guest
|
"Tom St Denis" <tomstdenis@iahu.ca> writes:
Quote: Problem is root finding is O(n^3) time and there are log2(n)/ln(log2(n))
prime exponents to test. So for n ~ 2^1024 there are 148 primes to test....
Even with a decently optimized root finder [the one in LTM could be written
slightly better] it's still going to take a while.
Unless I miss something, you need to test bases, not exponents.
What's to optimize? If you have some 1024 bit N and you want to know
if it's a power of 137, just compute y=ln(N)/ln(137) with floating
point arithmetic, and if y is near enough to being an integer, check
whether 137**round_to_nearest_int(y)==N. If y isn't very close to
an integer, you don't even need to bother with the exact integer test. |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Sat Jan 03, 2004 10:45 pm |
|
|
|
Guest
|
"Paul Rubin" <http://phr.cx@NOSPAM.invalid> wrote in message
news:7x4qvcmmf8.fsf@ruckus.brouhaha.com...
Quote: "Tom St Denis" <tomstdenis@iahu.ca> writes:
Problem is root finding is O(n^3) time and there are log2(n)/ln(log2(n))
prime exponents to test. So for n ~ 2^1024 there are 148 primes to
test....
Even with a decently optimized root finder [the one in LTM could be
written
slightly better] it's still going to take a while.
Unless I miss something, you need to test bases, not exponents.
What's to optimize? If you have some 1024 bit N and you want to know
if it's a power of 137, just compute y=ln(N)/ln(137) with floating
point arithmetic, and if y is near enough to being an integer, check
whether 137**round_to_nearest_int(y)==N. If y isn't very close to
an integer, you don't even need to bother with the exact integer test.
I'm trying todo this in LTM. I can't assume a float support exists.
Tom |
|
|
| Back to top |
|
| |
