Elon Musks Prime Number Check

Main.Swift

//
//  main.swift
//  Miller-Rabin
//
//  Created by Mark Cornelisse on 26/06/2025.
//

// Create a Mac Command Line App with xcode. Copy this entire file in the main.swift

import Cocoa

struct BigInt {
    let words: [UInt64] // Little-endian: words[0] is least significant

    // Initialize from an array of 22 UInt64 words for 1400 bits
    init(words: [UInt64]) {
        assert(words.count == 22, "Expected 22 UInt64 words for 1400 bits")
        self.words = words
    }

    // Check if the number is even
    var isEven: Bool {
        return words[0] % 2 == 0
    }

    // Subtract 1 from BigInt (assumes self > 1)
    func minusOne() -> BigInt {
        var result = self.words
        var borrow: UInt64 = 1
        for i in 0..<words.count {
            let sub = words[i] &- borrow
            result[i] = sub
            borrow = (sub > words[i]) ? 1 : 0
            if borrow == 0 { break }
        }
        return BigInt(words: result)
    }

    // Divide by 2 (right shift by 1 bit)
    func dividedByTwo() -> BigInt {
        var result = [UInt64](repeating: 0, count: words.count)
        for i in (1..<words.count).reversed() {
            result[i] = (words[i] >> 1) | (words[i-1] << 63)
        }
        result[0] = words[0] >> 1
        return BigInt(words: result)
    }

    // Compare two BigInts
    func lessThan(_ other: BigInt) -> Bool {
        for i in (0..<words.count).reversed() {
            if words[i] < other.words[i] { return true }
            if words[i] > other.words[i] { return false }
        }
        return false
    }

    // Multiply two BigInts
    func multiply(_ other: BigInt) -> BigInt {
        var result = [UInt64](repeating: 0, count: words.count * 2)
        for i in 0..<words.count {
            for j in 0..<other.words.count {
                let (high, low) = words[i].multipliedFullWidth(by: other.words[j])
                let k = i + j
                var carry: UInt64 = 0
                let sumLow = result[k] &+ low
                carry = (sumLow < low) ? 1 : 0
                result[k] = sumLow
                let sumHigh = result[k + 1] &+ high &+ carry
                carry = (sumHigh < high || (carry > 0 && sumHigh == high)) ? 1 : 0
                result[k + 1] = sumHigh
                var t = k + 2
                while carry > 0 && t < result.count {
                    let sum = result[t] &+ carry
                    carry = (sum < carry) ? 1 : 0
                    result[t] = sum
                    t += 1
                }
            }
        }
        return BigInt(words: Array(result[0..<words.count]))
    }

    // Modulo operation (simplified subtraction-based)
    func modulo(_ n: BigInt) -> BigInt {
        var remainder = self
        while !remainder.lessThan(n) {
            var temp = n
            var shift = 0
            while !remainder.lessThan(temp) && shift < 63 {
                temp = BigInt(words: temp.words.map { $0 << 1 })
                shift += 1
            }
            if shift > 0 {
                temp = BigInt(words: temp.words.map { $0 >> 1 })
                shift -= 1
            }
            var result = remainder.words
            var borrow: UInt64 = 0
            for i in 0..<n.words.count {
                let sub = result[i] &- temp.words[i] &- borrow
                result[i] = sub
                borrow = (sub > result[i] || (borrow > 0 && sub == result[i])) ? 1 : 0
            }
            remainder = BigInt(words: result)
        }
        return remainder
    }

    // Modular exponentiation using square-and-multiply
    func powMod(_ exponent: BigInt, modulus: BigInt) -> BigInt {
        var result = BigInt(words: [1] + [UInt64](repeating: 0, count: 21))
        var base = self.modulo(modulus)
        var exp = exponent
        while !exp.words.allSatisfy({ $0 == 0 }) {
            if exp.isEven {
                base = base.multiply(base).modulo(modulus)
                exp = exp.dividedByTwo()
            } else {
                result = result.multiply(base).modulo(modulus)
                exp = exp.minusOne()
            }
        }
        return result
    }
}

// Miller-Rabin primality test for a 1400-bit unsigned integer
func isProbablyPrime(_ n: BigInt, rounds: Int = 20) -> Bool {
    // Base cases
    let two = BigInt(words: [2] + [UInt64](repeating: 0, count: 21))
    let three = BigInt(words: [3] + [UInt64](repeating: 0, count: 21))
    if n.words.allSatisfy({ $0 == 0 }) || n.words == [1] + [UInt64](repeating: 0, count: 21) {
        return false
    }
    if n.words == two.words { return true }
    if n.words == three.words { return true }
    if n.isEven { return false }

    // Write n-1 as 2^s * d
    var d = n.minusOne()
    var s = 0
    while d.isEven {
        d = d.dividedByTwo()
        s += 1
    }

    // Witness loop
    for _ in 0..<rounds {
        // Random base a in [2, n-2]
        // For simplicity, use small bases like 2, 3, 5, etc., since random number generation is limited
        let a = two // In practice, this should be random; here, we use 2 as a sample base
        var x = a.powMod(d, modulus: n)
        let one = BigInt(words: [1] + [UInt64](repeating: 0, count: 21))
        let nMinusOne = n.minusOne()
        if x.words == one.words || x.words == nMinusOne.words {
            continue
        }
        var continueOuter = false
        for _ in 0..<s-1 {
            x = x.powMod(two, modulus: n)
            if x.words == nMinusOne.words {
                continueOuter = true
                break
            }
        }
        if continueOuter { continue }
        return false
    }
    return true
}

extension BigInt {
    /// Initializes a BigInt from a decimal string representation.
    /// - Parameter decimalString: A string containing a decimal number (e.g., "12345").
    init(decimalString: String) {
        // Remove all non-numeric characters from the string
        let cleanedString = decimalString.filter { $0.isNumber }
        
        // Initialize to zero if the string is empty
        var current = BigInt(words: [UInt64](repeating: 0, count: 22))
        let ten = BigInt(words: [10] + [UInt64](repeating: 0, count: 21))
        
        // Process each digit from left to right
        for char in cleanedString {
            if let digit = UInt64(String(char)) {
                // Multiply current value by 10 and add the new digit
                current = current.multiply(ten).add(BigInt(words: [digit] + [UInt64](repeating: 0, count: 21)))
            }
        }
        self.words = current.words
    }
    
    /// Adds another BigInt to this one, handling carry across words.
    /// - Parameter other: The BigInt to add.
    /// - Returns: A new BigInt representing the sum.
    func add(_ other: BigInt) -> BigInt {
        var result = [UInt64](repeating: 0, count: words.count)
        var carry: UInt64 = 0
        
        // Add words with carry propagation
        for i in 0..<words.count {
            let sum = words[i] &+ other.words[i] &+ carry
            result[i] = sum
            carry = (sum < words[i] || (carry > 0 && sum == words[i])) ? 1 : 0
        }
        return BigInt(words: result)
    }
}

// Example usage (assuming n is a 1400-bit number represented as 22 UInt64 words)
// let n = BigInt(words: [/* 22 UInt64 values */])
// let isPrime = isProbablyPrime(n)

let largeNumberAsAString = """
    808888888888888888888888888888
    888888888888888888888888888888
    888888888888811118888888118888
    888888888811111111118811188888
    888888881111118888881111888888
    888888811118888888111111188888
    888888811188888811188111188888
    888888811188881118888811188888
    888888811118888888888111888888
    888888881118888888111111888888
    888888811181111111111188888888
    888881188888111111188888888888
    888888888888888888888888888888
    888888888888888888888888888881
"""
let largeNumber = BigInt(decimalString: largeNumberAsAString)
let isPrime = isProbablyPrime(largeNumber)
print(isPrime)