Tom's post a few days ago about turning strings into numbers made me wonder
if the ASCII-to-number of a person's name is a prime number. This Friday
evening I coded the console command below that asks for string names and
tests if the resulting BigInteger class made from the ASCII bytes is
probably prime. Some random sampling code (not shown) hints that the chance
of a string composed from the typical frequency distribution of the English
alphabet has about a 2% chance of being prime. So if your name is prime then
you are 1 in 50 special.
But seriously, the System.Numerics namespace in Framework 4.0 was a surprise
arrival, but it's a shame it's so small with containing two classes. A
"BigDecimal" class would have been an impressive addition.
Greg
using System;
using System.Text;
using System.Linq;
using System.Numerics;
namespace bigintplay
{
/// <summary>
/// A bit of nonsense that takes a string (expected to be a person's
name), gets the
/// ASCII bytes, reverses the byte into little endian order, constructs a
BigInteger
/// from the reversed bytes and then checks if the result it a probable
prime number.
/// Primality testing is done by trial division of small primes and also
by the Fermat
/// probablistic test (look it up to see why it's probabilistic due to
those damned
/// Carmichael numbers).
/// </summary>
public sealed class Program
{
const int FermatCount = 10;
static int[] smallPrimes =
{
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,1
03,107,109,113,
127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,
409,419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,
601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,
809,811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997
};
static void Main(string[] args)
{
NameChecker();
}
private static void NameChecker()
{
while (true)
{
Console.ResetColor();
Console.Write("Enter a name to test: ");
string name = Console.ReadLine();
if (name.Length == 0)
{
break;
}
Info("------------------------------------------------");
Info("Processing name\n\u25ba {0}", name);
byte[] rawbuff = Encoding.ASCII.GetBytes(name);
Info("Raw ASCII bytes\n\u25ba {0}", Hex(rawbuff));
byte[] littlebuff = rawbuff.Reverse().ToArray();
Info("Little endian\n\u25ba {0}", Hex(littlebuff));
BigInteger bi = new BigInteger(littlebuff);
Info("Number from little endian\n\u25ba {0}", bi);
bool failed = false;
var divs = (from s in smallPrimes where s < bi &&
BigInteger.Remainder(bi, s).IsZero select s);
if (divs.Any())
{
Console.ForegroundColor = ConsoleColor.Yellow;
Info("Trivial factors: {0}", string.Join(" ", (from div in divs
select div.ToString()).ToArray()));
failed = true;
}
for (int i = 0; i < FermatCount; i++)
{
int small = smallPrimes[i];
if (small < (bi - 1))
{
BigInteger mod = BigInteger.ModPow(small, bi - 1, bi);
if (!mod.IsOne)
{
Console.ForegroundColor = ConsoleColor.Yellow;
Info("Failed Fermat primality test for modulus {0}", small);
Console.ResetColor();
failed = true;
break;
}
}
}
if (failed)
{
Console.ForegroundColor = ConsoleColor.Red;
Info("YOUR NAME IS NOT PRIME");
}
else
{
Console.ForegroundColor = ConsoleColor.Cyan;
Info("Congratulations! Your name is probably prime");
Info("(the chance of this seems to be about 1 in 50)");
}
}
}
private static string Hex(byte[] buff)
{
return BitConverter.ToString(buff).Replace("-", "");
}
private static void Info(string format, params object[] args)
{
Console.WriteLine(format, args);
}
}
}
