#include "fe.h" #include "crypto_int64.h" #include "crypto_uint64.h" /*h = f * g Can overlap h with f or g . Preconditions : | f | bounded by 1 . 65 * 2 ^ 26 , 1 . 65 * 2 ^ 25 , 1 . 65 * 2 ^ 26 , 1 . 65 * 2 ^ 25 , etc . | g | bounded by 1 . 65 * 2 ^ 26 , 1 . 65 * 2 ^ 25 , 1 . 65 * 2 ^ 26 , 1 . 65 * 2 ^ 25 , etc . Postconditions : | h | bounded by 1 . 01 * 2 ^ 25 , 1 . 01 * 2 ^ 24 , 1 . 01 * 2 ^ 25 , 1 . 01 * 2 ^ 24 , etc . /*Notes on implementation strategy : Using schoolbook multiplication . Karatsuba would save a little in some cost models . Most multiplications by 2 and 19 are 32 - bit precomputations ; cheaper than 64 - bit postcomputations . There is one remaining multiplication by 19 in the carry chain ; one * 19 precomputation can be merged into this , but the resulting data flow is considerably less clean . There are 12 carries below . 10 of them are 2 - way parallelizable and vectorizable . Can get away with 11 carries , but then data flow is much deeper . With tighter constraints on inputs can squeeze carries into int32 . void fe_mul(fe h,const fe f,const fe g)0 ];1 ];2 ];3 ];4 ];5 ];6 ];7 ];8 ];9 ];0 ];1 ];2 ];3 ];4 ];5 ];6 ];7 ];8 ];9 ];19 * g1; /* 1.959375*2^29 */ 19 * g2; /* 1.959375*2^30; still ok */ 19 * g3;19 * g4;19 * g5;19 * g6;19 * g7;19 * g8;19 * g9;2 * f1;2 * f3;2 * f5;2 * f7;2 * f9;_19+f9g1_38;+f9g2_19;f9g3_38;19;_38;/* | h0 | < = ( 1 . 65 * 1 . 65 * 2 ^ 52 * ( 1 + 19 + 19 + 19 + 19 ) + 1 . 65 * 1 . 65 * 2 ^ 50 * ( 38 + 38 + 38 + 38 + 38 ) ) i . e . | h0 | < = 1 . 4 * 2 ^ 60 ; narrower ranges for h2 , h4 , h6 , h8 | h1 | < = ( 1 . 65 * 1 . 65 * 2 ^ 51 * ( 1 + 1 + 19 + 19 + 19 + 19 + 19 + 19 + 19 + 19 ) ) i . e . | h1 | < = 1 . 7 * 2 ^ 59 ; narrower ranges for h3 , h5 , h7 , h9 1 <<25 )) >> 26 ; h1 += carry0; h0 -= carry0 << 26 ;1 <<25 )) >> 26 ; h5 += carry4; h4 -= carry4 << 26 ;/* |h0| <= 2^25 */ /* |h4| <= 2^25 */ /* |h1| <= 1.71*2^59 */ /* |h5| <= 1.71*2^59 */ 1 <<24 )) >> 25 ; h2 += carry1; h1 -= carry1 << 25 ;1 <<24 )) >> 25 ; h6 += carry5; h5 -= carry5 << 25 ;/* |h1| <= 2^24; from now on fits into int32 */ /* |h5| <= 2^24; from now on fits into int32 */ /* |h2| <= 1.41*2^60 */ /* |h6| <= 1.41*2^60 */ 1 <<25 )) >> 26 ; h3 += carry2; h2 -= carry2 << 26 ;1 <<25 )) >> 26 ; h7 += carry6; h6 -= carry6 << 26 ;/* |h2| <= 2^25; from now on fits into int32 unchanged */ /* |h6| <= 2^25; from now on fits into int32 unchanged */ /* |h3| <= 1.71*2^59 */ /* |h7| <= 1.71*2^59 */ 1 <<24 )) >> 25 ; h4 += carry3; h3 -= carry3 << 25 ;1 <<24 )) >> 25 ; h8 += carry7; h7 -= carry7 << 25 ;/* |h3| <= 2^24; from now on fits into int32 unchanged */ /* |h7| <= 2^24; from now on fits into int32 unchanged */ /* |h4| <= 1.72*2^34 */ /* |h8| <= 1.41*2^60 */ 1 <<25 )) >> 26 ; h5 += carry4; h4 -= carry4 << 26 ;1 <<25 )) >> 26 ; h9 += carry8; h8 -= carry8 << 26 ;/* |h4| <= 2^25; from now on fits into int32 unchanged */ /* |h8| <= 2^25; from now on fits into int32 unchanged */ /* |h5| <= 1.01*2^24 */ /* |h9| <= 1.71*2^59 */ 1 <<24 )) >> 25 ; h0 += carry9 * 19 ; h9 -= carry9 << 25 ;/* |h9| <= 2^24; from now on fits into int32 unchanged */ /* |h0| <= 1.1*2^39 */ 1 <<25 )) >> 26 ; h1 += carry0; h0 -= carry0 << 26 ;/* |h0| <= 2^25; from now on fits into int32 unchanged */ /* |h1| <= 1.01*2^24 */ 0 ] = h0;1 ] = h1;2 ] = h2;3 ] = h3;4 ] = h4;5 ] = h5;6 ] = h6;7 ] = h7;8 ] = h8;9 ] = h9;
Messung V0.5 in Prozent C=89 H=100 G=94
¤ Dauer der Verarbeitung: 0.13 Sekunden
(vorverarbeitet am 2026-10-08)
¤ *© Formatika GbR, Deutschland
