Re: patch for Montgomery-style reduction in Flxq_pow

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Tue, Jan 20, 2004 at 12:48:44AM +0100, Bill Allombert wrote:
> Hello Pari-dev,
> 
> Here a new patch that implement Montgomery-style reduction
> for Flxq_pow.
> 
> i	:	tmg	:	mon	:	rem
> 1	:	0	:	50	:	40
> 2	:	0	:	30	:	30
> 3	:	0	:	20	:	20
> 4	:	0	:	20	:	10
> 5	:	0	:	30	:	20
> 6	:	0	:	30	:	30
> 7	:	0	:	50	:	50
> 8	:	0	:	70	:	90
> 9	:	0	:	100	:	170
> 10	:	20	:	150	:	340
> 11	:	80	:	220	:	670
> 12	:	310	:	330	:	1320
> 13	:	1220	:	510	:	2650
> 14	:	4920	:	760	:	5520
> 15	:	19750	:	1170	:	11430
> 
> (this is with the PARI kernel, GMP would be faster)
Here the result with the PARI kernel

1       :       0       :       60      :       40
2       :       0       :       30      :       30
3       :       0       :       20      :       20
4       :       0       :       20      :       20
5       :       0       :       20      :       20
6       :       0       :       30      :       20
7       :       0       :       30      :       40
8       :       0       :       40      :       90
9       :       0       :       50      :       170
10      :       20      :       60      :       340
11      :       80      :       90      :       670
12      :       310     :       120     :       1320
13      :       1220    :       160     :       2640
14      :       4930    :       210     :       5560
15      :       19750   :       250     :       11420

So we get a x40 speed up here.

I need to implement a faster Montgomery inverse. This one run in 
quadratic time. Ideas welcome.

Cheers,
Bill