Circle domain plotter

CircleDomainPlotter.tsx

import React, { useEffect, useState, useRef } from 'react';
import { getInitialDomainOfSize, M17 } from '@site/src/scripts/MerseneField';

import styles from "./styles.module.css";
import clsx from 'clsx';

const CircleDomainPlot: React.FC<{ width: string, height: string }> = ({ width, height }) => {
    const [step, setStep] = useState(4);

    useEffect(() => {
        import('plotly.js-dist-min').then((Plotly) => {
            // Function to generate domain points
            function generateDomainPoints(size) {
                const domain = getInitialDomainOfSize(M17, size);
                return domain;
            }

            // Generate initial domain points
            let initialDomain = generateDomainPoints(2 ** step);

            // Generate data for the initial domain points
            let domainPlotData = {
                x: initialDomain.map(([x, y]) => x.value),
                y: initialDomain.map(([x, y]) => y.value),
                mode: 'markers',
                marker: { color: 'blue', size: 10 },
                type: 'scatter'
            };

            const p = new M17(0).modulus;
            const pd2 = p / 2;

            
            // Layout for the plot
            let layout = {
                title: 'Initial Points on Unit Circle',
                xaxis: { title: 'x', tickvals: [0, pd2, p], ticktext: ['0', 'p/2', 'p'], color: '#bdbdbd' },
                yaxis: { title: 'y', tickvals: [0, pd2, p], ticktext: ['0', 'p/2', 'p'], color: '#bdbdbd' },
                showlegend: false,
                paper_bgcolor: 'rgba(0,0,0,0)',
                plot_bgcolor: 'rgba(0,0,0,0)',
                font: { color: '#E3E3E3' }
            };

            let config = {
                staticPlot: true
            };

            // Render the plot with the unit circle and initial points
            Plotly.newPlot('plot', [domainPlotData], layout, config);

            // Function to update the plot based on slider value
            function updatePlot(value) {
                const size = parseInt(value);
                const domainPoints = generateDomainPoints(2 ** size);
                domainPlotData.x = domainPoints.map(([x, y]) => x.value);
                domainPlotData.y = domainPoints.map(([x, y]) => y.value);
                domainPlotData.marker.color = '#FFEC3D';
                layout.title = `Domain Points (Size = ${2 ** size})`;
                Plotly.react('plot', [domainPlotData], layout);
            }

            // Update the plot initially and when step changes
            updatePlot(step);

        });
    }, [step]);

    return (
        <div className={clsx(styles.Illustation)}>
            <div id="plot" style={{ width, height, display: 'inline-block' }}></div>
            <div className={clsx(styles.InputRange)}>
                <label htmlFor="slider">Domain size</label>
                <input
                    type="range"
                    min="3"
                    max="10"
                    step="1"
                    value={step}
                    id="slider"
                    onChange={(e) => setStep(parseInt(e.target.value))}
                />
            </div>
        </div>
    );
};

export default CircleDomainPlot;

Mersenne.ts

class FieldElement {
    value: number;
    modulus: number;

    constructor(value: number, modulus: number) {
        this.modulus = modulus;
        this.value = value % this.modulus;
    }

    add(other: number | FieldElement): FieldElement {
        const othervalue = other instanceof FieldElement ? other.value : other;
        return new FieldElement((this.value + othervalue) % this.modulus, this.modulus);
    }

    sub(other: number | FieldElement): FieldElement {
        const othervalue = other instanceof FieldElement ? other.value : other;
        return new FieldElement(((this.value - othervalue) % this.modulus + this.modulus) % this.modulus, this.modulus);
    }

    neg(): FieldElement {
        return new FieldElement(this.modulus - this.value, this.modulus);
    }

    mul(other: number | FieldElement): FieldElement {
        const othervalue = other instanceof FieldElement ? other.value : other;
        return new FieldElement((this.value * othervalue) % this.modulus, this.modulus);
    }

    pow(other: number): FieldElement {
        return new FieldElement(modularExponentiation(this.value, other, this.modulus), this.modulus);    }

    inv(): FieldElement {
        if (this.value === 0) return new FieldElement(0, this.modulus);
        return new FieldElement(modInverse(this.value, this.modulus), this.modulus);
    }

    sqrt(): FieldElement {
        if (this.modulus % 4 !== 3) throw new Error("Modulus must be 3 mod 4");
        return this.pow((this.modulus + 1) / 4);
    }

    div(other: number | FieldElement): FieldElement {
        if (typeof other === 'number') other = new FieldElement(other, this.modulus);
        return this.mul((other as FieldElement).inv());
    }

    eq(other: number | FieldElement): boolean {
        const othervalue = other instanceof FieldElement ? other.value : other;
        return this.value === othervalue;
    }

    toString(): string {
        return `<${this.value}>`;
    }

    toBytes(): Uint8Array {
        return new Uint8Array(new Uint32Array([this.value]).buffer);
    }

    static fromBytes(bytez: Uint8Array, modulus: number): FieldElement {
        return new FieldElement(new Uint32Array(bytez.buffer)[0], modulus);
    }
}

export class M5 extends FieldElement {
    constructor(value: number) {
        super(value, (1 << 5) - 1);
    }
}

export class M17 extends FieldElement {
    constructor(value: number) {
        super(value, (1 << 17) - 1);
    }
}

export class M31 extends FieldElement {
    constructor(value: number) {
        super(value, (1 << 31) - 1);
    }
}

type Point = [FieldElement, FieldElement];

function log2(x: number): number {
    if ((x & (x - 1)) !== 0) throw new Error("x must be a power of 2");
    return Math.log2(x);
}

function pointAdd(pt1: Point, pt2: Point): Point {
    const [x1, y1] = pt1;
    const [x2, y2] = pt2;
    return [x1.mul(x2).sub(y1.mul(y2)), x1.mul(y2).add(x2.mul(y1))];
}

function pointDouble(pt: Point): Point {
    const [x1, y1] = pt;
    return [x1.mul(x1).mul(new FieldElement(2, x1.modulus)).sub(new FieldElement(1, x1.modulus)), x1.mul(y1).mul(new FieldElement(2, y1.modulus))];
}

function pointMultiply(pt: Point, n: number): Point {
    if (n === 0) return [new FieldElement(1, pt[0].modulus), new FieldElement(0, pt[0].modulus)];
    if (n === 1) return pt;
    const half = pointMultiply(pt, Math.floor(n / 2));
    const doubled = pointDouble(half);
    return n % 2 === 0 ? doubled : pointAdd(doubled, pt);
}

function getGenerator(field: new (value: number) => FieldElement): Point {
    const modulus = new field(0).modulus;
    for (let y = 2; y < modulus; y++) {
        const Y_pt = new field(y);
        const X_pt = new field(1 - y * y).sqrt();
        let point: Point = [X_pt, Y_pt];
        for (let i = 0; i < log2(modulus + 1) - 1; i++) {
            point = pointDouble(point);
        }
        if (!point[0].eq(1) || !point[1].eq(0)) {
            return [X_pt, Y_pt];
        }
    }
    throw new Error("Could not find generator");
}

export function getInitialDomainOfSize(field: new (value: number) => FieldElement, size: number): Point[] {
    const modulus = new field(0).modulus;
    if (size >= modulus) throw new Error("Size must be less than modulus");
    let G = getGenerator(field);
    for (let i = 0; i < log2((modulus + 1) / size) - 1; i++) {
        G = pointDouble(G);
    }
    const Gx2 = pointDouble(G);
    const domain = [G];
    for (let i = 1; i < size; i++) {
        domain.push(pointAdd(domain[domain.length - 1], Gx2));
    }
    return domain;
}

// Utility function for modular exponentiation
function modularExponentiation(base: number, exponent: number, modulus: number): number {
    if (modulus === 1) return 0;
    let result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

// Utility function for modular inverse
function modInverse(a: number, modulus: number): number {
    let m0 = modulus, t, q;
    let x0 = 0, x1 = 1;

    if (modulus === 1) return 0;

    while (a > 1) {
        q = Math.floor(a / modulus);
        t = modulus;
        modulus = a % modulus;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0) x1 += m0;
    return x1;
}