As usual, after dealing with a challenge, which taught me something, I looked around to see how my solution differs from others. And this time mine turned out to be rather unique.

No, it's not good (and even not excellent). =) I wanted to see how people solvedmodexp part, and I was interested in Rust solutions. All I opened were usingmodpow function ofbigint crate.

After all it said "write your own modexp", and it felt as a useful part of the exercise. So I employedcrypto_bigint crate, and constructed a function for this particular exercise. It's slow and limited to work with 192 bytes integers, but it's still capable to inspire you to tackle this challenge. (Also it should have a problem with exceed bit for big enough numbers, you can take a bigger bigint type if you want to avoid it.)

usecrypto_bigint::{U1536,Checked,NonZero,Random,rand_core::OsRng,Encoding,U3072};usesha3::{Sha3_256,Digest};fnmain(){letp=U1536::from_be_hex("ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff");letg=U1536::from(2u64);leta=U1536::random(&mutOsRng);leta_big=modexp(g,a,p);letb=U1536::random(&mutOsRng);letb_big=modexp(g,b,p);lets=modexp(b_big,a,p);println!("{s}");letmuthasher=Sha3_256::new();hasher.update(s.to_be_bytes());letresult=hasher.finalize();println!("{result:?}");}fnmodexp(base:U1536,exponent:U1536,modulus:U1536)->U1536{ifmodulus==U1536::ONE{returnU1536::ZERO;}letmodulus_ch=Checked::new(modulus);/* This algorithm is mostly based on Wikipedia    listing, and the next line is to test the     assertion they have. `unwrap`s below turned out     to be much more useful during debuggig. */(modulus_ch-Checked::new(U1536::ONE))*(modulus_ch-Checked::new(U1536::ONE));letmutresult=Checked::new(U3072::ONE);letmutbase=U1536::from(base);letmutbase=base%NonZero::new(modulus).unwrap();letmutbase=U3072::from_be_bytes(pad192(base));letmutbase=Checked::new(base);letmutmodulus=U3072::from_be_bytes(pad192(modulus));letmutexponent=exponent;whileexponent>U1536::ZERO{ifexponent%NonZero::new(U1536::from(2u64)).unwrap()==U1536::ONE{result=Checked::new((result*base).0.unwrap()%NonZero::new(modulus).unwrap());}exponent>>=1;base=Checked::new((base*base).0.unwrap()%NonZero::new(modulus).unwrap());}/* It should be checked that excessive bytes are     zero, but today we omit the check. They really     should after `% p` */U1536::from_be_slice(result.0.unwrap().to_be_bytes()[192..].into())}fnpad192(uint_192:U1536)->[u8;384]{letmutres:[u8;384]=[0;384];res[192..].copy_from_slice(&uint_192.to_be_bytes());res}

fn at Rosetta is more ubiquitous, but you still can get the values from there to test this one, created with another crate. Don't forget to make themU1536.

If you want to copy-paste them to employfrom_be_hex, here they are:
a:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006ED80FFACE4DF443C2E9A56155272B9004E01F5DABE5F2181A603DA3EB
b:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005737DF12ECACC95FF94E28463B3CD1DE0C674CB5D079BD3F4C037E48FF
modulus:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001D6329F1C35CA4BFABB9F5610000000000