PrimeScript

PrimeScript is an esoteric programming language designed by User:AndrewBayly in 2026. It is based on JavaScript, but encoded in such a way that running a program requires solving a computationally hard mathematical problem — specifically, integer factorisation. Writing a PrimeScript program is trivial. Interpreting one is, depending on your choice of parameters, anywhere between mildly inconvenient and cosmologically impossible.

PrimeScript inverts the usual relationship between human effort and machine effort. A programmer writes ordinary JavaScript. The encoder converts it to a single large integer in milliseconds. The interpreter must then factor that integer — a problem for which no efficient classical algorithm is known — before it can read a single token of the source.

Computational model

A PrimeScript program is a single positive integer N, constructed as follows:

Encoding

1. Take the JavaScript source text and encode it as a UTF-8 byte sequence.
2. Interpret that byte sequence as a big-endian integer m.
3. Generate a large random prime P of a chosen bit length k.
4. Compute N = m × P.
5. The program is N. Distribute N. Discard nothing else — but keep P private if you want the program to remain unrunnable.

Decoding

1. Find the factor of N whose bit-length is exactly k.
2. Call that factor P. Compute m = N / P.
3. Interpret m as a big-endian UTF-8 byte sequence.
4. Execute the result as JavaScript.

The decoder does not need to know P in advance. It needs only to know k, the bit length of P, which is part of the language specification for a given PrimeScript variant. The convention resolves the ambiguity inherent in factorisation: given two factors of N, the one with exactly k bits is P, and the other is m.

Why N = m × P, not a semiprime

A natural first instinct is to make N a semiprime — a product of exactly two large primes — so that both factors are hard to find. This does not work as intended, because m (the source text as an integer) is almost certainly composite. UTF-8 text interpreted as an integer will typically be even (and divisible by many small primes), so m is not prime and cannot be made prime without significant additional work at encode time.

The construction N = m × P therefore makes no claim that m is prime. Only P is prime. The hardness comes entirely from the size of P: finding a k-bit prime factor of N is equivalent to the RSA factorisation problem for that key size.

A further subtlety: because m is composite, fully factoring N into primes would reveal all prime factors of m as well as P, with no obvious way to reassemble m. The decoder therefore does not fully factor N. It searches specifically for a prime factor of exactly k bits, stops when it finds one, and divides. This is the correct and complete decoding procedure.

The bit-length convention

The choice of k is the central design parameter of any PrimeScript program. It controls how long the interpreter must work before the program can execute. Approximate classical estimates using the General Number Field Sieve (GNFS):

k (bits)	Approximate decode time (classical hardware)
16	Milliseconds
32	Seconds to minutes
64	Years
128	Millions of years
256	~10¹⁵ years
512	~10³⁰ years
1024	~10⁵⁰ years
2048	~10²⁰ core-years (many orders of magnitude beyond the age of the universe)

The 2048-bit case deserves a note. Gidney and Ekerå (2019, updated 2025) showed that a sufficiently large quantum computer — on the order of one million noisy qubits — could factor a 2048-bit number in under a week using Shor's algorithm. No such machine exists as of 2026. Classically, 2048-bit PrimeScript programs are write-only: they can be encoded, distributed, and admired, but never run.

Hello, World

The following is a valid PrimeScript program (16-bit P, for demonstration purposes):

The source text is:

console.log('Hello World');

Encoded as UTF-8, this is 27 bytes, which as a big-endian integer is:

m = 543618919699834133349842839830394734073901407587

Multiplied by a randomly chosen 16-bit prime P (for example, P = 40253):

N = 21880158847559636205032838486005872019225793261311

The decoder finds the factor of N with exactly 16 bits, recovers m, decodes it as UTF-8, and executes console.log('Hello World');.

A different execution of the encoder will produce a different N for the same source text, because P is chosen fresh each time. All such N are valid programs.

Properties

• Turing-complete: PrimeScript programs, once decoded, execute as JavaScript. JavaScript is Turing-complete, therefore PrimeScript is Turing-complete — in the same way that a book sealed in concrete is still a book.

• Write-once: At sufficiently large k, no PrimeScript program has ever been executed, and none ever will be. The language specification is complete and correct. The programs simply cannot be run.

• Non-deterministic encoding: The same source text encodes to a different N every time, because P is chosen randomly. The number of valid PrimeScript encodings of any given program is large but finite — exactly one for each k-bit prime. By the prime number theorem, there are approximately 2^k / (k × ln 2) such primes, which for large k is an enormous number, but a definite one.

• Self-delimiting: No separator, header, or metadata is required. N is the entire program. The bit length k is part of the language variant specification, not the program itself.

• Asymmetric by design: Encoding runs in O(k²) time (prime generation via Miller-Rabin). Decoding runs in time exponential in k (no known sub-exponential classical algorithm for general factorisation). This asymmetry is the point.

Philosophical notes

PrimeScript belongs to a tradition of esolangs that make execution the hard part — but unlike languages that achieve this through arbitrary obfuscation, PrimeScript grounds its difficulty in a well-studied open problem in mathematics. The hardness is not a trick. It is the same hardness that underpins RSA encryption, on which a significant fraction of global internet security currently depends.

There is something clarifying about a language in which the question "can this program run?" has a definite answer — yes, in principle; no, in practice — and where the gap between those two answers is measured in units like "the age of the universe" or "the heat death of the cosmos." PrimeScript makes vivid the distinction between a program that is correct and a program that is executable.

It also raises a question the language does not answer: if a program cannot be run, in what sense does it compute?

Reference implementation

A reference encoder and interactive decoder (for 16-bit and 32-bit P, suitable for demonstration) is available as a standalone HTML file using the Web Crypto API and JavaScript BigInt arithmetic. The encoder generates P using the Miller-Rabin primality test. The decoder searches for a k-bit prime factor of N by trial division in a Web Worker, reporting progress as it goes.

The decoder is intentionally slow and illustrative. A production decoder for 32-bit P would use a sieve to eliminate candidates divisible by small primes, reducing the search space by roughly 80%. For k ≥ 64, no practical decoder is known.

See also

• Malbolge — execution difficulty through deliberate obfuscation
• Brainfuck — minimalism in language design
• Befunge — unconventional program representation

External links

• Reference implementation (encoder + interactive decoder): PrimeScript

References

• Gidney, C. and Ekerå, M. (2019). How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits. arXiv:1905.09749.
• Gidney, C. (2025). How to factor 2048-bit RSA integers with less than a million noisy qubits. arXiv:2505.15917.
• Pomerance, C. (1996). A tale of two sieves. Notices of the AMS. (GNFS complexity background.)