Add Stark101 tutorial's prime field

[erhant]

trafficstars

Add Stark101 Prime Field

Description

I have been implementing the Stark101 tutorial using LambdaWorks (see here), and I had implemented the field used within the tutorial.

The prime field order is 3 * 2^30 + 1, which is FFT-friendly, however I cant implement the IsFFTFriendly trait for this custom field because the custom field is constructed as shown below:

#[derive(Clone, Debug, Hash, Copy, Serialize, Deserialize)]
pub struct MontgomeryConfigStark101PrimeField;
impl IsModulus<U64> for MontgomeryConfigStark101PrimeField {
    const MODULUS: U64 = U64::from_hex_unchecked("c0000001");
}

pub type Stark101PrimeField = U64PrimeField<MontgomeryConfigStark101PrimeField>;

which means that Stark101PrimeField is an alias of the U64PrimeField which does not belong to my crate, therefore I cant implement IsFFTFriendly (which also does not belong to my crate) to it.

The solution is therefore to add the field directly to LambdaWorks itself, and use it.

[!NOTE]

Although it is ok to use the non-FFT interpolation for the tutorial, which is used for interpolating over 1024 elements, I think its nice that we have the opportunity to use FFT as well. If not, one can complete the tutorial by implementing the field themselves.

Type of change

• [x] New feature: Added Stark101 prime field

Checklist

• [ ] Linked to Github Issue
• [x] Unit tests added
• [ ] This change requires new documentation.
  • [ ] Documentation has been added/updated.
• [ ] This change is an Optimization
  • [ ] Benchmarks added/run