mp_modexp_cpu.cc
/* assumes ar is 'montgomeritized' */
assumes ar is 'montgomeritized'
assumes ar is ' montgomeritized '
void mp_modexp_cpu(WORD *ret, const WORD *ar, const WORD *e, 
		const WORD *n, const WORD *np)
{
	struct mp_sw sw;
	WORD ar_sqr[MAX_S];
	mp_get_sw(&sw, e);
	WORD ar_pow[MP_SW_MAX_FRAGMENT / 2][MAX_S];
	for (int i = 0; i < MAX_S; i++)
		ar_pow[0][i] = ar[i];
	mp_montmul_cpu(ar_sqr, ar_pow[0], ar_pow[0], n, np);
	for (int i = 3; i <= sw.max_fragment; i += 2)
		mp_montmul_cpu(ar_pow[i >> 1], ar_pow[(i >> 1) - 1], ar_sqr, n, np);
	for (int i = 0; i < MAX_S; i++)
		ret[i] = ar_pow[sw.fragment[sw.num_fragments - 1] >> 1][i];
	for (int k = sw.num_fragments - 2; k >= 0; k--) {
		for (int i = 0; i < sw.length[k]; i++)
			mp_montmul_cpu(ret, ret, ret, n, np);
		if (sw.fragment[k])
			mp_montmul_cpu(ret, ret, ar_pow[sw.fragment[k] >> 1], n, np);
	}
}
void mp_modexp_cpu ( WORD * ret , const WORD * ar , const WORD * e , const WORD * n , const WORD * np ) { struct mp_sw sw ; WORD ar_sqr [ MAX_S ] ; mp_get_sw ( & sw , e ) ; WORD ar_pow [ MP_SW_MAX_FRAGMENT / 2 ] [ MAX_S ] ; for ( int i = 0 ; i < MAX_S ; i ++ ) ar_pow [ 0 ] [ i ] = ar [ i ] ; mp_montmul_cpu ( ar_sqr , ar_pow [ 0 ] , ar_pow [ 0 ] , n , np ) ; for ( int i = 3 ; i <= sw . max_fragment ; i += 2 ) mp_montmul_cpu ( ar_pow [ i >> 1 ] , ar_pow [ ( i >> 1 ) - 1 ] , ar_sqr , n , np ) ; for ( int i = 0 ; i < MAX_S ; i ++ ) ret [ i ] = ar_pow [ sw . fragment [ sw . num_fragments - 1 ] >> 1 ] [ i ] ; for ( int k = sw . num_fragments - 2 ; k >= 0 ; k -- ) { for ( int i = 0 ; i < sw . length [ k ] ; i ++ ) mp_montmul_cpu ( ret , ret , ret , n , np ) ; if ( sw . fragment [ k ] ) mp_montmul_cpu ( ret , ret , ar_pow [ sw . fragment [ k ] >> 1 ] , n , np ) ; } }
assumes ar is 'montgomeritized'
assumes ar is ' montgomeritized '
/* odd powers of ar (ar, (ar)^3, (ar)^5, ... ) */