Mark Udstrand

Greenhorn

Posts: 4

posted 5 years ago

I am calculating h/g^x1 in Zp. I have java code that generates the correct value, but it run exponentially slower as the numbers get bigger, and I am not sure why I am seeing such a dramatic slow down. The code is as follows;

How can this be changed to make the performance linear instead of exponential?

How can this be changed to make the performance linear instead of exponential?

Campbell Ritchie

Marshal

Posts: 56545

172

posted 5 years ago

Welcome to the Ranch , even though you resisted posting for the best part of five years!

How do you know it is running in exponential time? What sort of performance figures do you have?

Your base enlarges continually; it has something like 200 digits in (too long for the screen, and you can see from above how to split such lines), so its length would increase by 200 digits every iteration.

How do you know it is running in exponential time? What sort of performance figures do you have?

Your base enlarges continually; it has something like 200 digits in (too long for the screen, and you can see from above how to split such lines), so its length would increase by 200 digits every iteration.

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 5 years ago

I did a quick timing test and it looks to me like the run time per iteration is increasing linearly - which would make the overall runtime quadratic (n^2, where n is the number of iterations). Which is about what we would expect if the number of digits in the base is increasing linearly with each iteration, and all the major operations here take time linearly proportional to the number of digits. Is there some particular reason to expect it to be better?

You might want to look at other arbitrary-precision mathematical libraries, like GMP. There are some faster arithmetic algorithms out there than what BigInteger uses. (E.g. see this list of multiplication algorithms used by GMP. I'm not very familiar with the various libraries you might use, however, so I can't say much more than that.

You might want to look at other arbitrary-precision mathematical libraries, like GMP. There are some faster arithmetic algorithms out there than what BigInteger uses. (E.g. see this list of multiplication algorithms used by GMP. I'm not very familiar with the various libraries you might use, however, so I can't say much more than that.

posted 5 years ago

Well, you have a few things in play here:

1. Mike is right: there are probably faster "big" value classes out there; especially in projects dedicated to Maths. I think of Java's as a "general purpose" big integer, and the performance is generally adequate for an app guy like me.

2. BigIntegers are immutable, which means that the result of any calculation has to be copied to a new instance. In a highly specialized environment like a maths library, it's quite possible that you don't have to worry about niceties like Thread-safety and can make all numbers mutable.

3. I suspect the real problem is your division. The

4. Java doesn't have unsigned integers (except for

HIH

Winston

Mark Udstrand wrote:How can this be changed to make the performance linear instead of exponential?

Well, you have a few things in play here:

1. Mike is right: there are probably faster "big" value classes out there; especially in projects dedicated to Maths. I think of Java's as a "general purpose" big integer, and the performance is generally adequate for an app guy like me.

2. BigIntegers are immutable, which means that the result of any calculation has to be copied to a new instance. In a highly specialized environment like a maths library, it's quite possible that you don't have to worry about niceties like Thread-safety and can make all numbers mutable.

3. I suspect the real problem is your division. The

`pow()`method does use repeated squaring (to be honest I have no idea if there are any faster methods now), but division seems to be pretty much as you'd expect.

4. Java doesn't have unsigned integers (except for

`char`), which means that there's quite a lot of conversion and masking of

`int`s to and from

`long`s. It seems to me that they

*might*have been able to gain some speed by using

`char`s and

`int`s instead; but maybe it's outweighed by the fact that you'd then have extra operations. It's also possible that they work a bit quicker on 64-bit JVMs, but I honestly don't know.

HIH

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Mark Udstrand

Greenhorn

Posts: 4

Campbell Ritchie

Marshal

Posts: 56545

172

posted 5 years ago

As Campbell says: well done.

One tiny point:

I was also wondering why it's

Winston

Mark Udstrand wrote:Okay, I have a much better solution now so I thought I would share.

As Campbell says: well done.

One tiny point:

`new Hashtable<BigInteger, Integer>(1048577)`will create a Hashtable that doesn't need to be rehashed while it's being filled. Also: HashMap is usually preferred these days.

I was also wondering why it's

`Hashtable<BigInteger, Integer>`rather than

`Hashtable<Integer, BigInteger>`? The latter would seem more likely to me; but I'm not exactly sure how you're using

`hgMod`.

Winston

Articles by Winston can be found here

Mark Udstrand

Greenhorn

Posts: 4

posted 5 years ago

I had it scaled in a earlier code revision and simply forgot to carry it forward. I was so concentrated on the math that I overlooked this clear optimization, thanks!

It is this way to aid in the fastest search possible. I am doing a meet in the middle cipher attack (for a cryptography class) and the second part of the algorithm calculates BigInteger values that are then used to search the hash. Since there are potentially 1M+ searches into this hash, the fastest search possible is desirable. With a hashmap that happens to be the containsKey() method.

One tiny point: new Hashtable<BigInteger, Integer>(1048577) will create a Hashtable that doesn't need to be rehashed while it's being filled. Also: HashMap is usually preferred these days.

I had it scaled in a earlier code revision and simply forgot to carry it forward. I was so concentrated on the math that I overlooked this clear optimization, thanks!

I was also wondering why it's Hashtable<BigInteger, Integer> rather than Hashtable<Integer, BigInteger>? The latter would seem more likely to me; but I'm not exactly sure how you're using hgMod.

It is this way to aid in the fastest search possible. I am doing a meet in the middle cipher attack (for a cryptography class) and the second part of the algorithm calculates BigInteger values that are then used to search the hash. Since there are potentially 1M+ searches into this hash, the fastest search possible is desirable. With a hashmap that happens to be the containsKey() method.