From wstein@ucsd.edu Thu Feb 16 17:04:00 2006
From: William Stein <wstein@ucsd.edu>
Organization: UC San Diego
To: Barry Smith <barryrsmith@gmail.com>
Subject: Re: bernfrac
Date: Thu, 16 Feb 2006 17:04:00 -0800
User-Agent: KMail/1.9.1
References: <200601082158.34196.wstein@ucsd.edu> <5850a51c0602161614p322616f4rc531cbf4be749296@mail.gmail.com>
In-Reply-To: <5850a51c0602161614p322616f4rc531cbf4be749296@mail.gmail.com>
X-KMail-Link-Message: 558000
X-KMail-Link-Type: reply
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200602161704.01083.wstein@ucsd.edu>
Status: RO
X-Status: RSC
X-KMail-EncryptionState:  
X-KMail-SignatureState:  
X-KMail-MDN-Sent:  

On Thursday 16 February 2006 16:14, you wrote:
> Thanks for your previous e-mail about bernfrac.  I found your talk
> today very interesting.  I have a couple of results whereby I can
> calculate class numbers of cyclic cubic fields of prime conductor p
> for primes p of the form p = (a^2 + 27)/4 and of the form p = (1 +
> 27*b^2)/4 if I can compute a couple of Bernoulli numbers.  In
> particular, in the first case, the class number h is characterized by
> the congruence
>
> h \equiv -3/2 B_{r}/r B_{2*r}/(2*r) mod p where r is (p-1)/3
>
> and in the second case,
>
> h \equiv -1/18 B_{r}/r B_{2*r}/(2*r) mod p where r is (p-1)/3.
>
> I have been toying with the idea of making a big table of class
> numbers, but I am not very tech savvy and I have a lot to work on as
> it is.

Cool.  This is exactly the sort of thing I hoped you'd get interested
in when I saw your talks.  We can do something together, since it
might be a nice application of the table of B_k for all k < 10^5 that 
I'm computing right now (and which will be done in a day, since the
computer is computing above 95000 right now).   

> Also, I have been wondering if calculating the inverses of numbers mod
> p would be any faster than the usual algorithm using the following
> algorithm:
> if you want the inverse of a mod p, run the Euclidean algorithm with
> a*p + 1 and p^2 as your starting values instead of a and p.  The first
> remainder you get that is less than p is the inverse of a mod p.  It
> saves you the trouble of having to backtrack once you find that the
> GCD of a,p is 1, but on the other hand, you have to make a comparison
> of the remainder with p at each step.  The number of steps to reach
> the inverse in my method can be shown to be the same as the number of
> steps to reach the GCD when running the Euclidean algorithm with a and
> p.  Of course, the original algorithm is so fast that I don't suppose
> it matters.  I just think mine is charming, and a little mysterious.

I don't know.  It would be fun to implement just to watch it run.  
There are also supposedly subquadratic asymptotically fast (x)gcd
algorithms, which might be relevant to the above.  I just don't
know.  Explaining your algorithm would be a really good idea for
the graduate student research seminar.  I'm trying to find some students
to talk so I can start it up again.  (I didn't do it in January since
I was busy preparing for SAGE days.)

William