pow_mod() incredibly slow

[PrisionMike]

Yet another learner writing yet another code to generate prime numbers.

I am trying to run the fermat_little primality test.

I realised that it made the code incredibly slow. I am aware many systems like PGP and some forks of SSL do implement it so it shouldn't be impractical to use it. I realise the botleneck to be the Int::pow_mod() It takes about 600 700 ms to run the particular operation.

I wanted to know if I am doing anything wrong here. Following is the code:

fn fermat_little(n: &Int) -> bool {

    let mut rng = thread_rng();
    let called = Instant::now();

    let somea: Int = rng.gen_uint_below(n);

    let brought_the_rand = called.elapsed();

    let res = somea.pow_mod( &(n - Int::one()) , n );

    let did_the_powmod = called.elapsed();

    println!("Took {:?} to generate a rand brat.\n{:?} to do the pow mod",brought_the_rand,did_the_powmod);

    res == Int::one()
}

[PrisionMike]

I am genrating 2048 bit prime numbers. WHile writing the above comment I ran the entire code, here's what the output looks like now (I disabled testing with smaller primes to achieve marginal gains in speed):

Took 33.6µs to generate a rand brat.
638.1421ms to do the pow mod
The prime is:
14713937144288049819278536516739271837018275812754935987795080433488036474034857018008337810047501641606956085703070152511800876451066100437434554480835396136898546494279471557655514449434290524382458163231252214910852849794217211861162926044074095072681630049791298997295403849747105443416376157844158750394602636861764637857997422359028878458072612559789618187896993000856023337963468674316645115967584385309298908447024554461173515319587987623140494591147482644004696392581479859463213918276235970575810245695996630685637110475439238300543146160607995876069958934000966309842556186461588180968584918820784845740939

found at the 1556th attempt

[PrisionMike]

running it in --release mode brought down to ~20ms (or perhaps less). Here's to hoping that's fast enough for all intents and purposes.