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

I'm trying todo this in LTM. I can't assume a float support exists.

"Tom St Denis" <tomstdenis@iahu.ca> writes:
I'm trying todo this in LTM. I can't assume a float support exists.

Just approximate it then. A simple 3 or 4 bit table lookup and a
little bit of interpolation should be fine. See "Numerical Recipes"
by Teukolsky et al for fancier ways to do approximations like that.
Don't obsess your mind on that cryptography stuff, get outside and do
some real programming now and then .

"Tom St Denis" <tomstdenis@iahu.ca> writes:
I'm trying todo this in LTM. I can't assume a float support exists.

Just approximate it then. A simple 3 or 4 bit table lookup and a
little bit of interpolation should be fine. See "Numerical Recipes"
by Teukolsky et al for fancier ways to do approximations like that.
Don't obsess your mind on that cryptography stuff, get outside and do
some real programming now and then .

Technically I could use a fixed point representation for ln(x) for x < some
constant [like 6500 or so is around the 256th prime]. So I use 32-bits as a
fraction. The trick now is to find ln(x) with at least 32-bits of
resolution. I think your method is a tad too simple since your "y" may be
off by a few value [we are dealing with huge numbers here].

Technically I could use a fixed point representation for ln(x) for x < some
constant [like 6500 or so is around the 256th prime]. So I use 32-bits as a
fraction. The trick now is to find ln(x) with at least 32-bits of
resolution. I think your method is a tad too simple since your "y" may be
off by a few value [we are dealing with huge numbers here].

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

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

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.

Sorry, I don't quite follow this. How does it generalize? You
repeat the above calculation with 137 replaced by ... what?

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

"Paul Rubin" <http://phr.cx@NOSPAM.invalid> wrote in message
news:7xoetkl60g.fsf@ruckus.brouhaha.com...
"Tom St Denis" <tomstdenis@iahu.ca> writes:
I'm trying todo this in LTM. I can't assume a float support exists.

Just approximate it then. A simple 3 or 4 bit table lookup and a
little bit of interpolation should be fine. See "Numerical Recipes"
by Teukolsky et al for fancier ways to do approximations like that.
Don't obsess your mind on that cryptography stuff, get outside and do
some real programming now and then .

Technically I could use a fixed point representation for ln(x) for x < some
constant [like 6500 or so is around the 256th prime]. So I use 32-bits as a
fraction. The trick now is to find ln(x) with at least 32-bits of
resolution.

"Tom St Denis" <tomstdenis@iahu.ca> writes:
"Paul Rubin" <http://phr.cx@NOSPAM.invalid> wrote in message
news:7xoetkl60g.fsf@ruckus.brouhaha.com...
"Tom St Denis" <tomstdenis@iahu.ca> writes:
I'm trying todo this in LTM. I can't assume a float support exists.

Just approximate it then. A simple 3 or 4 bit table lookup and a
little bit of interpolation should be fine. See "Numerical Recipes"
by Teukolsky et al for fancier ways to do approximations like that.
Don't obsess your mind on that cryptography stuff, get outside and do
some real programming now and then .

Technically I could use a fixed point representation for ln(x) for x < some
constant [like 6500 or so is around the 256th prime]. So I use 32-bits as a
fraction. The trick now is to find ln(x) with at least 32-bits of
resolution.

For the problem in hand, you only need to calculate as many bits as are
required to know that the final answer is not an integer.
50% of the time, you'll not need to go beyond 3 bits, I'm sure.

For the problem in hand, you only need to calculate as many bits as are
required to know that the final answer is not an integer.
50% of the time, you'll not need to go beyond 3 bits, I'm sure.

Phil,

I don't quite understand. What do you want to approximate with 3 bits?