Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Signed bits and fast exponentiation

Wieb Bosma — 2001

Journal de théorie des nombres de Bordeaux

An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that...

On the computation of quadratic 2 -class groups

Wieb Bosma;  Peter Stevenhagen — 1996

Journal de théorie des nombres de Bordeaux

We describe an algorithm due to Gauss, Shanks and Lagarias that, given a non-square integer D ≡ 0 , 1 mod 4 and the factorization of D , computes the structure of the 2 -Sylow subgroup of the class group of the quadratic order of discriminant D in random polynomial time in log D .

Page 1

Download Results (CSV)