“Finite Field Arithmetic.” Chapter 17: Introduction to Peh.

This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical “Open Sores” abomination, in that — rather than trusting the author blindly with their lives — prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.

Chapter 16B, the M-R proof, has been postponed; it will appear towards the end of the series.

You will need:

Add the above vpatches and seals to your V-set, and press to ffa_ch17_peh.kv.vpatch.

You should end up with the same directory structure as previously.

FFACalc is gone! But it was reborn as… see below.

As of Chapter 17, the versions of Peh and FFA are 252 and 253, respectively.

Now compile Peh:

cd ffacalc
gprbuild

But do not run it quite yet.


First, the mail bag!


Reader bvt has given me to know that he has read and signed Chapters 7 – 9:

He also published a report of his interesting experiment with ASM-accelerated multiplication.

Thank you, reader bvt!


Now, let’s eat the meat of this Chapter.


LibFFA per se is unchanged (aside from the removal of a single “uniturd” from a single comment) from Chapter 16A, as reflected in the version numbers. No major changes to LibFFA per se are expected to be necessary from this point onward.

FFACalc, the “toy” demonstration program of FFA, is no more. With the addition of certain necessary (why — will become apparent to the reader…) features, it has pupated into a simple “FORTH-like” interpreter “machine”, titled: Peh. These features, and the mechanisms of their implementation, will be the subject of this Chapter.

We will begin by summarizing the Peh instruction set, as it stands in this Chapter:

Peh Instruction Set.
Op Description # Ins # Outs Notes
Blocks
( Enter Comment Block 0 0 All further symbols are ignored until comment block is exited; supports nesting.
) Exit Comment Block 0 0 Fatal if not currently in a comment block.
[ Enter Quote Block 0 0 All further symbols are not executed, but instead echoed verbatim until quote block is exited; supports nesting.
] Exit Quote Block 0 0 Fatal if not in a quote block.
{ Enter Conditional Branch 1 0 Pop top item from stack; if it was non-zero, execute all symbols until a matching } exits the conditional block; otherwise ignore them until same; supports nesting. Fatal if stack is empty.
} Exit Conditional Branch 0 1 Pushes a 1 to stack if the branch being exited had been taken, otherwise pushes a 0.
Stack Motion
" Dup 1 2 Push a copy of the top item to the stack.
_ Drop 1 0 Discard the item on top of stack
' Swap 2 2 Exchange top and second item on stack
` Over 2 3 Push a copy of second item to stack
Constants
. Push Zero 0 1 Push a brand-new zero to stack
0..9, A..F, a..f Insert Hexadecimal Digit 1 1 Insert the given hexadecimal digit as the junior-most nibble into the top item on stack. Fatal if stack is empty. Equivalent to top := (16 × top) + Digit.
Predicates
= Equals 2 1 Push a 1 on stack if the top and second items are bitwise-equal; otherwise 0
< Less-Than 2 1 Push a 1 on stack if the second item is less than the top item
> Greater-Than 2 1 Push a 1 on stack if the second item is greater than the top item
Bitwise
& Bitwise-AND 2 1 Compute bitwise-AND of the top and second item, push result on stack
| Bitwise-OR 2 1 Compute bitwise-OR of the top and second item, push result on stack
^ Bitwise-XOR 2 1 Compute bitwise-XOR of the top and second item, push result on stack
~ Bitwise-Complement 1 1 Compute 1s-complement negation of the top item on stack, i.e. flip all bits of it.
U Bitwise-MUX 3 1 If top item is nonzero, a copy of the second item will be pushed to the stack; otherwise – of the third item.
W Width-Measure 1 1 Calculate the position of the senior-most bit in the top item that equals 1 (or return 0 if there are none) and push this number to stack.
RS Right-Shift 2 1 Shift the second item right by the number of bits given in the top item modulo the FZ bitness.
LS Left-Shift 2 1 Shift the second item left by the number of bits given in the top item modulo the FZ bitness.
Arithmetic: Basic
- Subtract 2 1 Subtract top item from second item, push result on stack, and save borrow bit into Flag
+ Add 2 1 Add top and second item, push result to stack, and save carry bit into Flag
O Push Overflow Flag 0 1 Push a copy of Flag, the register containing carry or borrow from the most recent arithmetic op, to the stack
Arithmetic: Division
\ Divide with Remainder 2 2 Divide second item by top item, push quotient and then remainder on stack; division by zero is fatal
/ Divide without Remainder 2 1 Divide second item by top item, push only quotient on stack; division by zero is fatal
% Modulus 2 1 Divide second item by top item, push only remainder on stack; division by zero is fatal
G Greatest Common Divisor 2 1 Find the Greatest Common Divisor of the top and second item, and push to the stack. GCD(0,0) is conventionally defined as 0.
Arithmetic: Multiplication
* Multiply 2 2 Multiply second item and top item, push the junior half of the result on stack, and then the senior half
R* Right-Multiply 2 1 Multiply top and second item, and push only the junior half of the product to the stack. The “Low-Multiply” from Ch. 14B.
S Square 1 2 Square the top item, put the junior half of the result on stack, and then the senior half
Arithmetic: Modular
MS Modular Square 2 1 Square the second item modulo the top item and push the result (necessarily fits in one FZ) to the stack. division by zero is fatal.
M* Modular Multiplication 3 1 Multiply third item and second item, modulo the top item; push the result to stack (necessarily fits in one FZ); division by zero is fatal
MX Modular Exponentiation 3 1 Raise third item to the power of the second item, modulo the top item, push the result to stack (necessarily fits in one FZ); division by zero is fatal.
Arithmetic: Primes
P Perform a single shot of the Miller-Rabin Monte Carlo Primality Test on N, the second item on the stack, using the top item as the Witness parameter for the test. Push a 1 to the stack if N was found to be composite; or a 0, if N was not found to be composite. 2 1 If the supplied Witness does not satisfy the inequality 2 ≤ Witness ≤ N - 2 , it will be mapped via modular arithmetic to a value which satisfies it.
N ∈ {0, 1} will be pronounced composite under any Witness; N ∈ {2, 3} will be judged not composite under any Witness.
Any N which was found to be composite under any particular Witness, is in fact composite. The converse, is however, not true; see Ch. 16 discussion.
Registers
$g, $h, ... $z Stack to Register 1 0 Pop top item from the stack, and assign to one of registers gz. The previous value of the register is discarded.
g, h, ... z Register to Stack 0 1 Push the current value of selected register: gz to the stack. Register retains its current value.
I/O
# Print FZ 1 0 Output top item to the standard output, in hexadecimal representation.
? Random 0 1 Fill a FZ from the active RNG and put on stack. Takes potentially-unbounded time, depending on the machine RNG.
Control
: Push Tape Position 0 0 Push the current Tape Position to the control stack. Does not affect the data stack.
; Unconditional Return 0 0 Pop a Tape Position from the control stack, and transfer control there upon the next tick. Underflowing the control stack is fatal.
, Conditional Return 1 0 Pop a Tape Position from the control stack; pop top item from stack, and if it is non-zero then transfer control to the new Tape Position upon the next tick. Underflowing the control stack is fatal.
Halting
QY Quit with ‘Yes’ Verdict 0 0 Halt Peh with a Verdict of Yes.
QN Quit with ‘No’ Verdict 0 0 Halt Peh with a Verdict of No.
QM Quit with ‘Mu’ Verdict 0 0 Halt Peh with a Verdict of Mu.
QD Quit with ‘Mu’ Verdict and Debug Trace 0 0 Halt Peh with a Verdict of Mu, and print debug trace.
QE Quit with Eggog 0 0 Halt Peh and signal a catastrophic error.
Other
V Push the Peh and FFA version numbers to the stack. 0 2 Kelvin Versioning is in use.
Z Zap 0 0 Reset Data Stack, Registers, and Flag.
Not Yet Defined:
! Undefined 0 0 Prohibited
@ Undefined 0 0 Prohibited
H Undefined 0 0 Prohibited
I Undefined 0 0 Prohibited
J Undefined 0 0 Prohibited
K Undefined 0 0 Prohibited
N Undefined 0 0 Prohibited
T Undefined 0 0 Prohibited
X Undefined 0 0 Prohibited (outside of MX)
Y Undefined 0 0 Prohibited

Please refer to this table as you read on.


Previously, in FFACalc, command symbols were interpreted strictly sequentially. Thereby it was possible to use the system strictly interactively, and to enter a potentially-infinite sequence of commands. This is not possible if we wish (and for certain purposes, we do) to have nonlinear control flow. Therefore we trade away the “infinity”, in exchange for a “batch” model of command input.

The operator is to invoke Peh just like FFACalc before, i.e. with a Width and Height specification, but additionally with a specification of spatial and time bounds for the Peh Tape execution:

Usage: ./peh WIDTH HEIGHT TAPESPACE LIFE [/dev/rng]

… and from that point, Peh will accept a certain number of symbols on the “standard input”, until it reaches the TAPESPACE spatial bound; immediately after the specified TAPESPACE storage is filled (or an “end of file” marker is found on the “standard input”) the Peh Machine will execute a number of program steps bounded by LIFE (if LIFE is set to zero, the result is an “immortal” run — generally this mode of operation is useful strictly in Peh Tape development and novice exploration.)

To permit bidirectional motion across a Peh Tape, a Control Stack is implemented. But we will say more about this further below.

First, let’s review the data structure specifications and the “main” routine of Peh:

limits.ads:

package Limits is
 
   -- Maximum permitted length of a Peh Tape.
   -- Peh Tapes live on the iron stack, like everything else,
   -- so it is not possible to promise "infinite" storage space for them.
   Max_Peh_TapeSpace      : constant Positive := 1048576; -- 1MB
   -- Operator may enlarge this constant, but may have to adjust OS stack cap.
   -- On small/embedded systems, it can be made smaller, as appropriate.
 
   -- The exact height of the Peh Control Stack. This is an invariant.
   Peh_Control_Stack_Size : constant Positive := 256;
 
end Limits;

The internal mechanism of the interpreter is still titled “FFACalc”.

ffa_calc.ads:

package FFA_Calc is
 
   -- Peh Tapes:
   subtype Peh_Tape_Range is Positive range 1 .. Max_Peh_TapeSpace;
   type Peh_Tapes is array(Peh_Tape_Range range <>) of Character;
 
   -- Possible Verdicts of a non-erroneous Peh Tape run:
   type Peh_Verdicts is (Yes, No, Mu);
 
   -- Operator-Selectable Spatial and Time Dimensions of a Peh Machine:
   type Peh_Dimensions is
      record
         Width     : Positive;
         Height    : Positive;
         TapeSpace : Peh_Tape_Range;
         Life      : Natural;
      end record;
 
   -- Valid indices into the Control Stack:
   subtype ControlStack_Range is Natural range 0 .. Peh_Control_Stack_Size;
   -- The 'zero' position, as with the Data Stack, indicates 'emptiness'
   -- when pointed to by CSP ( see ffa_calc.adb ) and is never accessed.
 
   -- Ensure that requested Peh Dimensions are permissible. Terminate if not.
   procedure Validate_Peh_Dimensions(Dimensions : in Peh_Dimensions);
 
   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts;
 
end FFA_Calc;

peh.adb:

-- This is the 'main' procedure of Peh for all Unixlike OS.
procedure Peh is
 
   PehDim  : Peh_Dimensions; -- Operator-specified spacetime footprint.
 
   RNG     : RNG_Device;     -- The selected RNG device. Peh requires a RNG.
 
begin
 
   -- If a valid number of command line params was NOT given, print a likbez :
   if Arg_Count < 5 or Arg_Count > 6 then
      Eggog("Usage: ./peh WIDTH HEIGHT TAPESPACE LIFE [/dev/rng]");
   end if;
 
   declare
      Arg1 : CmdLineArg;
      Arg2 : CmdLineArg;
      Arg3 : CmdLineArg;
      Arg4 : CmdLineArg;
   begin
 
      -- Get commandline args:
      Get_Argument(1, Arg1); -- First  mandatory arg : Width
      Get_Argument(2, Arg2); -- Second mandatory arg : Height
      Get_Argument(3, Arg3); -- Third  mandatory arg : TapeSpace
      Get_Argument(4, Arg4); -- Fourth mandatory arg : Life
 
      if Arg_Count = 6 then
 
         -- A RNG was specified (Arg_Count includes program name itself)
         declare
            Arg5 : CmdLineArg;
         begin
            Get_Argument(5, Arg5); -- Fifth arg (optional) : RNG device
 
            -- Ada.Sequential_IO chokes on paths with trailing whitespace!
            -- So we have to give it a trimmed path. But we can't use
            -- Ada.Strings.Fixed.Trim, because it suffers from
            -- SecondaryStackism-syphilis. Instead we are stuck doing this:
            Init_RNG(RNG, Arg5(Arg5'First .. Len_Arg(5)));
         end;
 
      else
 
         -- If RNG was NOT explicitly specified:
         Init_RNG(RNG); -- Use the machine default. The '?' Op requires a RNG.
 
         -- Warn the operator that we are going to use the default system RNG:
         Achtung("WARNING: The '?' command will use DEFAULT entropy source : "
                   & Default_RNG_Path & " !");
         -- Generally, you do NOT want this, outside of noob exploration/tests.
 
      end if;
 
      -- Parse the four mandatory arguments into Positives:
      PehDim.Width     := Positive'Value(       Arg1 );
      PehDim.Height    := Positive'Value(       Arg2 );
      PehDim.TapeSpace := Peh_Tape_Range'Value( Arg3 );
      PehDim.Life      := Natural'Value(        Arg4 );
 
   exception
 
      -- There was an attempt to parse garbage in the init parameters:
      when others =>
         Eggog("Invalid arguments!");
 
   end;
 
   -- Validate requested Peh Dimensions. If invalid, program will terminate.
   Validate_Peh_Dimensions(PehDim);
 
   -- Read, from Unix 'standard input' , and then execute, the Tape:
   declare
 
      -- The current Tape input symbol
      Tape_Read_Char  : Character;
 
      -- The TapeSpace
      TapeSpace       : Peh_Tapes(1 .. PehDim.TapeSpace) := (others => ' ');
 
      -- 'End of File' condition when reading :
      EOF             : Boolean := False;
 
      -- Will contain the Verdict produced by the Tape:
      Verdict         : Peh_Verdicts;
 
   begin
 
      -- Attempt to read the entire expected Tapespace length, and no more:
      for TapePosition in TapeSpace'Range loop
 
         -- Attempt to receive a symbol from the standard input:
         if Read_Char(Tape_Read_Char) then
 
            -- Save the successfully-read symbol to the TapeSpace:
            TapeSpace(TapePosition) := Tape_Read_Char;
 
         else
 
            -- Got an EOF instead of a symbol:
            EOF := True;
            if TapePosition /= TapeSpace'Length then
               Achtung("WARNING: Short Tape: Tapespace filled to position:" &
                         Peh_Tape_Range'Image(TapePosition) & " of" &
                         Peh_Tape_Range'Image(TapeSpace'Last) & ".");
            end if;
 
         end if;
 
         exit when EOF; -- When EOF, halt reading, and proceed to execution.
 
      end loop;
 
      -- Execute Peh over the given Tape, on Peh Machine with given dimensions:
      Verdict := Peh_Machine(Dimensions => PehDim,
                             Tape       => TapeSpace,
                             RNG        => RNG);
 
      -- A correctly-written Peh Tape is expected to produce a Verdict.
      -- On Unix, we will give it to the caller process via the usual means:
      case Verdict is
 
         -- Tape produced a Verdict of 'Yes' :
         when Yes =>
            Quit(Yes_Code);
 
         -- Tape produced a Verdict of 'No'  :
         when No =>
            Quit(No_Code);
 
            -- Tape ran to completion without producing any Verdict at all.
            -- Outside of simple test scenarios, noob explorations, etc.,
            -- this usually means that there is a logical mistake in the
            -- Tape somewhere, and we will warn the operator:
         when Mu =>
            Achtung("WARNING: Tape terminated without a Verdict.");
            Quit(Mu_Code);
 
      end case;
 
      -- If the Tape aborted on account of a fatal error condition (e.g. div0)
      -- Peh will Quit(Sad_Code) (see E(..) in ffa_calc.adb .)
      -- Therefore, Peh ALWAYS returns one of FOUR possible Unix return-codes:
      -- -2, -1, 0, 1. (see os.ads .)
 
   end;
 
end Peh;


Apart from the new “batch input” system, the reader will also observe the presence of a new concept: the Verdict. Virtually all Peh Tapes will set forth to perform a particular computation which may succeed or fail, depending on the inputs (given as Peh Tapes may be fed into Peh back-to-back, the earlier Tape constituting an “input” for a subsequent Tape.) Therefore it is necessary to have a mechanism for proclaiming this success or failure to the operator (on Unixlike OS — the calling process.) Failure is distinguished into two types, as we will see further below.

The four possible Verdicts of a Peh run are Yes, No, Mu, and Eggog. Let’s discuss each of these, to remove any possible doubt as to their correct usage.

A verdict of Yes indicates a positive answer to the question being put to the machine (e.g. “is this a valid signature of the given payload by the given public key?”)

A verdict of No is the logical opposite of the above.

A verdict of Mu is meant to indicate that a Tape was not able to produce a logically-valid Verdict, for any reason that does not entail an irrecoverable arithmetical error (e.g. division by zero, or abuse of the stacks) in the program on the Tape. For example, in the event that a given computational input violates a particular agreed-upon format, Mu may be proclaimed. An empty tape will, unsurprisingly, result in a Verdict of Mu; as will any Tape that does not explicitly proclaim a different Verdict prior to its termination.

A verdict of Eggog indicates a “coarse error of pilotage” (e.g. stack over/underflow, division by zero, or another logically-impermissible – i.e. compromising the logical validity of any further instructions — condition) on the input Tape; or, alternatively, an explicit invocation of the QE instruction; or, elementarily, an invocation of Peh with incompletely-specified or prohibited spatial dimensions.

Verdicts, including Eggog, may be explicitly proclaimed by a Tape, using the Q operator prefix:

ffa_calc.adb:

      -- Execute a Prefixed Op
      procedure Op_Prefixed(Prefix : in Character;
                            O      : in Character) is
 
 .........     
 
      begin
 
         -- Which Prefix Op?
         case Prefix is
 
            ---------------------------------------------------------
            -- Quit...
            when 'Q' =>
 
               -- .. Quit how?
               case O is
 
                  -- ... with a 'Yes' Verdict:
                  when 'Y' =>
                     Verdict := Yes;
 
                  -- ... with a 'No' Verdict:
                  when 'N' =>
                     Verdict := No;
 
                  -- ... with a 'Mu' Verdict: (permitted, but discouraged)
                  when 'M' =>
                     IP_Next := IP; -- Force a 'Mu' Termination
 
                  -- ... with Debug Trace, and a 'Mu' Verdict:
                  when 'D' =>
                     Print_Trace;
                     IP_Next := IP; -- Force a 'Mu' Termination
 
                     -- ... with an explicit Tape-triggered fatal EGGOG!
                     -- The 'QE' curtain call is intended strictly to signal
                     -- catastrophic (e.g. iron) failure from within a Tape
                     -- program ('cosmic ray' scenario) where a ~hardwired
                     -- mechanism~ of any kind appears to have done something
                     -- unexpected; or to abort on a failed test of the RNG;
                     -- or similar hard-stop scenarios, where either physical
                     -- iron, or basic FFA routine must be said to have failed,
                     -- and the continued use of the system itself - dangerous.
                     -- The use of 'QE' for any other purpose is discouraged;
                     -- please do not use it to indicate failed decryption etc.
                  when 'E' =>
                     -- Hard-stop with this eggog:
                     E("Tape-triggered CATASTROPHIC ERROR! " &
                         "Your iron and/or your build of Peh, " &
                         "may be defective! Please consult " & 
                         "the author of this Tape.");
 
                     -- ... Unknown (Eggog):
                  when others =>
                     Undefined_Prefix_Op;
 
               end case;

… i.e. QY (”Yes”), QN (”No”), QM (”Mu”), QD (”Mu” with Debug Trace), and QE (”Eggog”, and please read the comment to learn the expected usage thereof.)

Observe that the “Yes” and “No” Verdicts can only result from an explicit proclamation, using the respective command, QY or QN.


Now let’s discuss the Control Stack, the new mechanism which permits bidirectional motion along a Tape, e.g. loops:

ffa_calc.adb:

 
   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts is
 
.........
 
      -- Valid indices into the Tape:
      subtype Tape_Positions is Peh_Tape_Range range Tape'First .. Tape'Last;
 
      -- Position of the CURRENT Op on the Tape:
      IP            : Tape_Positions;
 
      -- After an Op, will contain position of NEXT op (if = to IP -> halt)
      IP_Next       : Tape_Positions;
 
      -- Control Stack; permits bidirectional motion across the Tape:
      Control_Stack : array(ControlStack_Range) of Tape_Positions
        := (others => Tape_Positions'First);
 
      -- Current top of the Control Stack:
      CSP           : ControlStack_Range := ControlStack_Range'First;
 
.........
 
      -- Current Verdict. We run while 'Mu', tape remains, and Ticks under max.
      Verdict       : Peh_Verdicts := Mu;
 
.........
 
      -------------------
      -- Control Stack --
      -------------------
 
      -- Push a given Tape Position to the Control Stack:
      procedure Control_Push(Position : in Tape_Positions) is
      begin
         -- First, test for Overflow of Control Stack:
         if CSP = Control_Stack'Last then
            E("Control Stack Overflow!");
         end if;
 
         -- Push given Tape Position to Control Stack:
         CSP                := CSP + 1;
         Control_Stack(CSP) := Position;
      end Control_Push;
 
 
      -- Pop a Tape Position from the Control Stack:
      function Control_Pop return Tape_Positions is
         Position : Tape_Positions;
      begin
         -- First, test for Underflow of Control Stack:
         if CSP = Control_Stack'First then
            E("Control Stack Underflow!");
         end if;
 
         -- Pop a Tape Position from Control Stack:
         Position           := Control_Stack(CSP);
         Control_Stack(CSP) := Tape_Positions'First;
         CSP                := CSP - 1;
         return Position;
      end Control_Pop;
 
.........
 
   begin
      -- Reset all resettable state:
      Zap;
 
      -- Execution begins with the first Op on the Tape:
      IP := Tape_Positions'First;
 
      loop
 
         -- If current Op is NOT the last Op on the Tape:
         if IP /= Tape_Positions'Last then
 
            -- ... then default successor of the current Op is the next one:
            IP_Next := IP + 1;
 
         else
 
            -- ... but if no 'next' Op exists, or quit-with-Mu, we stay put:
            IP_Next := IP; -- ... this will trigger an exit from the loop.
 
         end if;
 
         -- Advance Odometer for every Op (incl. prefixes, in comments, etc) :
         Ticks := Ticks + 1;
 
         -- Execute the Op at the current IP:
         Op(Tape(IP));
 
         -- Halt when...
         exit when
           Verdict /= Mu or -- Got a Verdict, or...
           IP_Next  = IP or -- Reached the end of the Tape, or...
           Exhausted_Life;  -- Exhausted Life.
 
         -- We did not halt yet, so select the IP of the next Op to fetch:
         IP := IP_Next;
 
      end loop;
 
      -- Warn operator about any unclosed blocks:
      if CommLevel > 0 then
         Achtung("WARNING: Tape terminated with an unclosed Comment!");
      end if;
 
      if QuoteLevel > 0 then
         Achtung("WARNING: Tape terminated with an unclosed Quote!");
      end if;
 
      if CondLevel > 0 then
         Achtung("WARNING: Tape terminated with an unclosed Conditional!");
      end if;
 
      -- Warn operator if we terminated with a non-empty Control Stack.
      -- This situation ought to be considered poor style in a Peh Tape;
      -- for clarity, Verdicts should be returned from a place near
      -- the visually-apparent end of a Tape. However, this is not mandatory.
      if CSP /= Control_Stack'First then
         Achtung("WARNING: Tape terminated with a non-empty Control Stack!");
      end if;
 
      -- We're done with the Tape, so clear the state:
      Zap;
 
      -- Return the Verdict:
      return Verdict;
 
   end Peh_Machine;

Peh is an entirely conventional “dual-tape stack machine”. The Control Stack is not directly accessible to the operator, and is manipulated strictly by a small set of instruction symbols which facilitate “backwards” transfer of control along the Tape.

Let’s examine the three currently-defined instruction symbols which make use of the Control Stack:

ffa_calc.adb:

               -------------------
               -- Control Stack --
               -------------------
 
               -- Push current IP (i.e. of THIS Op) to Control Stack.
            when ':' =>
               Control_Push(IP);
 
               -- Conditional Return: Pop top of Stack, and...
               -- ... if ZERO:    simply discard the top of the Control Stack.
               -- ... if NONZERO: pop top of Control Stack and make it next IP.
            when ',' =>
               Want(1);
               declare
                  Position : Tape_Positions := Control_Pop;
               begin
                  if FFA_FZ_NZeroP(Stack(SP)) = 1 then
                     IP_Next := Position;
                  end if;
               end;
               Drop;
 
               -- UNconditional Return: Control Stack top popped into IP_Next.
            when ';' =>
               IP_Next := Control_Pop;

The : operator pushes the current (i.e. its own) position on the Tape to the Control Stack. (Observe that, just as with the Data Stack, overflow is prohibited and results in an Eggog Verdict.)

The ; operator pops a Tape Position from the Control Stack, and execution (as always, if the Life limit has not yet been reached) continues from that position. (Observe that, just as with the Data Stack, underflow is prohibited and results in an Eggog Verdict.)

The , operator is a conditional variant of the ; operation.

These three instructions can be used to implement loops. E.g.:

$ echo -n '.5:[foo].1-",_QY' | ./bin/peh 256 32 17 61 /dev/random

Results in the output:

foofoofoofoofoo

Nested loops are permitted, up to the limit imposed by the Control Stack depth. E.g.,

echo -n '.7:[a].5:[b].1-",_.1-",_QY' | ./bin/peh 256 32 27 405 /dev/random

… produces:

abbbbbabbbbbabbbbbabbbbbabbbbbabbbbbabbbbb

The ; operator (intended for returning from subroutine invocations, which will be introduced in the next Chapter!) can also be used to perform an “infinite” (in actuality, bounded by Life) loop. Generally you will not do this in a Peh Tape intended for distribution, but it is possible:

$ echo -n ':[a];' | ./bin/peh 256 32 6 13 /dev/random

… will output:

aaa
WARNING: Exhausted Life ( 13 ticks ) 
WARNING: Tape terminated with an unclosed Quote! 
WARNING: Tape terminated with a non-empty Control Stack! 
WARNING: Tape terminated without a Verdict.

The reader is invited to experiment with loops and their behaviour with respect to the Peh invocation parameters.

To aid in the development of Peh Tapes, the QD operator may be used to display a complete state dump and terminate (with verdict of Mu) a program under development. E.g.:

echo -n '.1.2.3:::QD' | ./bin/peh 256 32 27 405 /dev/random

… will yield:

WARNING: Short Tape: Tapespace filled to position: 12 of 27.
WARNING: Tape terminated with a non-empty Control Stack!
WARNING: Tape terminated without a Verdict.
Data Stack:
    3 : 0000000000000000000000000000000000000000000000000000000000000003
    2 : 0000000000000000000000000000000000000000000000000000000000000002
    1 : 0000000000000000000000000000000000000000000000000000000000000001
Control Stack:
    3 : 9
    2 : 8
    1 : 7
Registers:
    g : 0000000000000000000000000000000000000000000000000000000000000000
    h : 0000000000000000000000000000000000000000000000000000000000000000
    i : 0000000000000000000000000000000000000000000000000000000000000000
    j : 0000000000000000000000000000000000000000000000000000000000000000
    k : 0000000000000000000000000000000000000000000000000000000000000000
    l : 0000000000000000000000000000000000000000000000000000000000000000
    m : 0000000000000000000000000000000000000000000000000000000000000000
    n : 0000000000000000000000000000000000000000000000000000000000000000
    o : 0000000000000000000000000000000000000000000000000000000000000000
    p : 0000000000000000000000000000000000000000000000000000000000000000
    q : 0000000000000000000000000000000000000000000000000000000000000000
    r : 0000000000000000000000000000000000000000000000000000000000000000
    s : 0000000000000000000000000000000000000000000000000000000000000000
    t : 0000000000000000000000000000000000000000000000000000000000000000
    u : 0000000000000000000000000000000000000000000000000000000000000000
    v : 0000000000000000000000000000000000000000000000000000000000000000
    w : 0000000000000000000000000000000000000000000000000000000000000000
    x : 0000000000000000000000000000000000000000000000000000000000000000
    y : 0000000000000000000000000000000000000000000000000000000000000000
    z : 0000000000000000000000000000000000000000000000000000000000000000
Ticks : 11
IP    : 11

Warnings are sent to the “standard error” output stream under all Unixlike OS.


Now let’s discuss Registers. These are implemented quite simply:

ffa_calc.adb:

 
   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts is
 
.........
 
      -- Registers:
      subtype RegNames is Character range 'g' .. 'z';
      type RegTables is array(RegNames range <>) of FZ(1 .. Wordness);
      Registers     : RegTables(RegNames'Range);
 
.........
 
      -- Execute a Normal Op
      procedure Op_Normal(C : in Character) is
 
         -- Over/underflow output from certain ops
         F : Word;
 
      begin
 
         case C is
 
.........
 
               -------------------------
               -- Fetch from Register --
               -------------------------
            when 'g' .. 'z' =>
               Push;
               Stack(SP) := Registers(C); -- Put value of Register on stack
 
.........
 
 
      -- Execute a Prefixed Op
      procedure Op_Prefixed(Prefix : in Character;
                            O      : in Character) is
.........
 
      begin
 
         -- Which Prefix Op?
         case Prefix is
 
.........
 
            ---------------------------------------------------------
            -- Write into Register...
            when '$' =>
 
               -- Eggog if operator gave us a garbage Register name:
               if O not in RegNames then
                  E("There is no Register '" & O & "' !");
               end if;
 
               -- Selected Register exists; move top FZ on stack into it:
               Want(1);
               Registers(O) := Stack(SP);
               Drop;
.........

There are precisely 20 Registers: g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z.

Remember that the Peh system is case-sensitive.

A Register may be assigned a value by invoking the $ operator, followed by the name of the Register, e.g. $r. This will pop a FZ from the Data Stack and assign its value to the selected register.

To retrieve a value from a Register, it suffices to invoke the name of that register as a Peh command, e.g. r. This will place a copy of the current value of that register on the Data Stack.



In Chapter 18, we will introduce a subroutine mechanism to Peh.


~To be continued!~

X-Ray Large-Format Kindergarten.

Below is the output of a new test-fire of the PCB radiography system, this time using FujiFilm “Super HR-T Medium Speed” (25×20 cm) film in place of the earlier self-developing dental Eco-30.

However, the time has not yet come to molest the MacIvory — first, we must characterize the film and the pertinent chemistry.

This time, the victims were a FG TRNG Mainboard and Analogue RNG Board, and additionally a vintage Adaptec 2940 SCSI card.

Exposure: 45 sec. @ 35kV, in “Fuji” scintillator cassette; developed and fixed in “SDX” B&W developer and fixer, respectively 1 min. and 2min. each; with water as stop bath.


Fuji: hang


Adaptec 2940.
Click for full resolution (Warning: 35MB!)

Fuji: Adaptec


Adaptec 2940 Detail: CPU.
Click for full resolution (Warning: 16MB!)

Fuji: Adaptec


FG TRNG Mainboard.
Click for full resolution (Warning: 26MB!)

Fuji: FG MB


FG TRNG Analogue RNG Unit.
Click for full resolution (Warning: 25MB!)

Fuji: FG Analogue


The shadow artifacts are accounted for by the off-center placement of the film inside the cassette: the dead center of the beamline ended up in the bottom right-hand corner of the film. Scratches are to be blamed on the plastic trays; I’ve been informed that one ought to place sheet glass at the bottom of each tray when developing radiographic emulsion, but did not bother for this test. The results of this mistake are visible on the upper left hand corner of the Adaptec scan.

No fogging was observed, it would appear that — contrary to some reports — a traditional red “safelight” is entirely adequate for this film.

The obvious loss of resolution, however, is to be blamed on the scintillator: these infamously introduce blur. I suspect that the film per se, and the development chemistry, are entirely good as they stand. Future shots will be taken with a direct, cassette-less exposure, as soon as I find what can be used for a properly opaque bag for the Fuji film (as it is, it ships “naked”, in crates of 100.)

Edit: how do we know it’s the scintillator? The alert reader will observe, via the full-res images, that the grain of the Fuji film is finer than that of the Eco-30. This suggests that the new film per se is not to blame for the blur.

X-Ray Microscopy of Symbolics “Ivory” CPUs.

I currently have three Symbolics MacIvory CPUs. (Do you, reader, have one to sell? Please leave a comment!)

One is currently installed in a working machine and was not yet molested; the two remaining chips, I obtained in 2017 by bartering away a Symbolics 3620.

At some point I will cut one or more of the “Ivories” open, and perform die microscopy. But prior to this, why not a bit of non-destructive imaging?


The first of the two samples is a “production” model, with a metallic cap:

Click for full resolution (1 MB):

Iron Ivory

Edit: the bottom side of this unit looks like this.

An attempted die shot at maximum voltage yielded:

Click for full resolution (Warning: 20 MB!):

Iron Ivory


It appears that 35kV (the maximum setting of the system) is unable to produce a usefully-contrasting image of the die and connections.

So we move on to the second sample, a “proto” model with a ceramic cap:


Click for full resolution (200 kB):

Ceramic Ivory

And with this one, we get:

Click for full resolution (Warning: 20 MB!):

Ceramic Ivory


Pretty interesting. What is the substance visible on the die? (glue holding the lid in place? or a “bird’s eye” view of the metallic layers of the die itself?)

Later, a magnified shot will be taken of this unit, with 35cm film and a scintillation cassette.

Exposure: 75 sec. @ 35kV, contact print, film: “Eco-30″.


X-Ray Spectrography Kindergarten.

This article is a continuation of “X-Ray Microscopy Kindergarten.”.


Preliminary experiment with multi-energy x-ray (colour channel combination), distinguishing materials by absorption at different wavelengths.

FG CPLD MultiEnergy Xray

The tube appears to exhibit some “heel effect” at the longer wavelengths.

Exposure: 75 sec. @ 35kV, 21kV, 20kV (R, G, B) film: “Eco-30″.


X-Ray Stereography Kindergarten.

This article is a continuation of “X-Ray Microscopy Kindergarten.”.


Here, we see a stereo pair (approx. +/- 25 deg. one-axis rotation of the object from the horizontal plane, while film is stationary) of the device from before.

FG CPLD Stereograph

The vias are clearly distinguishable.

Exposure: 70 sec. @ 34kV; 0.3mA + 2x beam spread; film: “Eco-30″.


X-Ray Microscopy Kindergarten.

This article is a continuation of “PCB Radiography Kindergarten, Continued.”.


The radiography system is equipped with a “microfocus” tube, and its beam has a 30 degree spread cone. So we can get a look at that very same FG TRNG XC9572 CPLD seen earlier, but with 2x magnification:

Click for full resolution (Warning: 7MB)

FG CPLD 2x

This time, we can clearly distinguish the gold bonding wires which connect the silicon die to the pins.

Unfortunately, it is not possible to take a shot of the die surface using this type of instrument… (or is it..?)

Exposure: 85 sec. @ 34kV; 0.3mA + 2x beam spread; film: “Eco-30″.


PCB Radiography Kindergarten, Continued.

This article is a continuation of “PCB Radiography Kindergarten”.


This was a second test-fire of that radiography system, using yet-another board where I already know where everything is (on account of having designed it.)

This time, the victim is a FG TRNG Mainboard:

Click for full resolution (Warning: 16MB)

FG Mainboard

For comparison, a visible-light photograph of the same section:


FG Mainboard (optical)

Detail of XC9572 CPLD:


FG CPLD

Detail of 14.7456MHz quartz resonator:


FG Resonator

Exposure: 100 sec. @ 32kV, 0.3mA @ 25cm; film: “Eco-30″.


PCB Radiography Kindergarten.

Below is the result of test-firing a newly-installed miniature PCB radiography system.

The victim is a standard FG TRNG Analogue Unit:

Click for full resolution (Warning: 14MB)


FG Analogue

Detail of left op amp, with bonding whiskers visible:


FG Analogue Amp

The substrate, aluminum RF shield frame, SMT contacts, vias, and the two layers of the PCB are clearly distinguishable. Likewise resistors (nearly transparent) from capacitors (comparatively metal-heavy.)

Exposure: 100 sec. @ 32kV; 0.3mA @ 25cm. film: “Eco-30″.

More interesting applications — later.


Lost Technology: The PQ3QI-01 Sunlight-Readable Display.

In the last quarter of the previous year, I got hold of a virginal (sealed OEM-crate) PQ3QI-01 sunlight-viewable LCD panel (and, after several unsuccessful attempts — an old box where it fits.) These marvels are long out of print but apparently still available, somehow, from the Chinese, at around 100 $ per.

If the backlight lamp is used, even on minimal power, the colour picture remains sharp in direct sunlight, which cannot be said for any other LCD which I have previously owned.

When the lamp is not used, the reflective backing of the crystal becomes visible and makes for a razor-sharp monochrome picture, if the contents of the display are appropriately configured.

I promised several people a photograph, which follows:

Lamp enabled, Emacs in typical working mode:

pixelqi in sun with lamp on

Lamp disabled, and Emacs background set to white:

pixelqi in sun with lamp off

The spot of shade is the fault of my head plus the camera. Possibly I will re-take this picture when winter ends, for a clearer portrait, the above does not really do the thing justice.

The machine (otherwise uninteresting, and costing around 50 $ second-hand) was experimentally found to run, given a full charge, for 4.5 – 5 hours with the lamp running; and 7.5 – 8 without (given minimal CPU load.)

Before anyone asks, I have no idea why the manufacturer went broke. It was, IMHO, a great product, and in so far as I know had no competition whatsoever, nor is any direct replacement available today (aside from the Chinese old-stock.)

Posted in: Hardware, NonLoper, Photo by Stanislav No Comments

“Finite Field Arithmetic.” Chapter 16A: The Miller-Rabin Test.

This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical “Open Sores” abomination, in that — rather than trusting the author blindly with their lives — prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.

You will need:

Add the above vpatches and seals to your V-set, and press to ffa_ch16_miller_rabin.kv.vpatch.

You should end up with the same directory structure as previously.

As of Chapter 16, the versions of FFACalc and FFA are 253 and 253, respectively.

Now compile ffacalc:

cd ffacalc
gprbuild

But do not run it quite yet.


First, the mail bag!


Reader bvt has given me to know that he has read and signed Chapters 1 – 6:

He also published a report of his interesting experiment with a variant of the Karatsuba multiplication algorithm.

Thank you, reader bvt!


Now, let’s eat the meat of this Chapter.


We will add a very useful feature to FFA and FFACalc, a constant-spacetime Miller-Rabin Monte Carlo Primality Test:

Op Description # Ins # Outs Notes
P Perform a single shot of the Miller-Rabin Monte Carlo Primality Test on N, the second item on the stack, using the top item as the Witness parameter for the test. Places 1 on the stack if N was found to be composite; or 0, if N was not found to be composite. 2 1 If the supplied Witness does not satisfy the inequality 2 ≤ Witness ≤ N - 2 , it will be mapped via modular arithmetic to a value which satisfies it.
N ∈ {0, 1} will be pronounced composite under any Witness; N ∈ {2, 3} will be judged not composite under any Witness.
Any N which was found to be composite under any particular Witness, is in fact composite. The converse, is however, not true; see Ch. 16 discussion.

The proof of the Miller-Rabin method will be given in the next chapter, 16B.

Presently, the reader is invited to satisfy himself that the given program conforms to the stated variant of Miller-Rabin, and executes it in constant-spacetime:


Algorithm 1: Miller-Rabin Monte Carlo Primality Test.


For an odd integer N ≥ 5 and a positive integer Witness where 2 ≤ W ≤ N - 2:

  1. Find the unique values R ≥ 1 and odd K such that 2R × K = N - 1.
  2. T := WK mod N.
  3. If T ∈ {1, N - 1}:
       Return Possibly-Prime.
  4. Iterate R - 1 times:
  5.    T := T2 mod N
  6.    If T = N - 1:
       Return Possibly-Prime.
  7. Return Composite.


The astute reader will immediately observe that Algorithm 1 is not suitable for use in FFA, as it does not execute in constant time, and does not correctly handle all possible values of N: N < 5 and even N do not meet the stated constraints.

Additionally, given as most practical uses of the Miller-Rabin method involve a sequence of invocations with a random Witness parameter, it is necessary to force a potentially out-of-range Witness into the expected range, with a minimal loss of entropy.

So, let’s generalize the algorithm:


Algorithm 2: Generalized Miller-Rabin Monte Carlo Primality Test.


For
any integers N and W:


  1. ProbPrime  := 0.

  2. DegenComp  := {N ∈ {0, 1, even and ≠ 2} → 1, else 0}.

  3. DegenPrime := {N ∈ {2, 3} → 1, else 0}.

  4. BW        := W mod (N - 1).

  5. If BW < 2:
       BW := 2;
  6. Find the unique values R ≥ 1 and odd K such that 2R × K = N - 1.
  7. T := BWK mod N.
  8. If T ∈ {1, N - 1}:
       ProbPrime := 1.
  9. Iterate R - 1 times:
  10.    T := T2 mod N
  11.    If T = N - 1:
       ProbPrime := 1.
  12. If DegenComp = 1:
       Return Composite.
  13. If DegenPrime = 1 or ProbPrime = 1:
       Return Possibly-Prime.
  14. Return Composite.

Still not a constant-time algorithm; but the sharp reader will be able to identify the missing ingredients.

Now let’s rewrite it into a form suitable for use in FFA:


Algorithm 3: Constant-Time Generalized Miller-Rabin Monte Carlo Primality Test.


For
any integers N and W:


  1. DegenComp  := (N = 0) OR (N = 1) OR ((N ≠ 2) AND (N mod 2 = 0))

  2. DegenPrime := (N = 2) OR (N = 3)

  3. ProbPrime := DegenPrime.

  4. BW        := W mod (N - 1).

  5. BW        := Mux( 2 ← (BW < 2) , BW ← (BW ≥ 2) )
  6. R         := Count_Bottom_Zeros(N).
  7. K         := N >> R.
  8. T         := BWK mod N.
  9. ProbPrime := ProbPrime OR (T = 1) OR (T = N - 1)
  10. I         := 1
  11. Iterate FZ_Bitness(N) - 1 times:
  12.    T         := T2 mod N
  13.    ProbPrime := ProbPrime OR ((I < R) AND (T = N - 1))
  14.    I         := I + 1
  15. Return DegenComp OR (1 - ProbPrime).
  16. Returned value 0 corresponds to Possibly-Prime; 1 to Composite.

This variant will carry out the Miller-Rabin test on any possible candidate integer of a given FFA Bitness, without leaking the integer or the Witness via timing side-channel, and the Witness will be forced into the valid range. To my knowledge, this is the first publication of an algorithm which has these characteristics.

Without further delay, let’s implement Algorithm 3 as a FFA subroutine:


fz_prime.adb:

package body FZ_Prime is
 
   -- Find the highest power of 2 which divides N. ( or 0 if N is zero. )
   function FZ_Count_Bottom_Zeros(N : in FZ) return FZBit_Index is
 
      -- The result (default : 0, will remain 0 if N is in fact zero)
      Index     : Word := 0;
 
      -- The currently-examined Word, starting from the highest
      Ni        : Word;
 
      -- The most recently-seen nonzero Word, if indeed any exist
      W         : Word := 0;
 
      -- 1 if currently-examined Word is zero, otherwise 0
      NiZ       : WBool;
 
   begin
 
      -- Find lowest non-zero Word (or simply stop at lowest, if N = 0)
      for i in reverse 0 .. Indices(N'Length - 1) loop
         Ni    := N(N'First + i);              -- Ni := current Word;
         NiZ   := W_ZeroP(Ni);                 -- ... is this Word = 0?
         Index := W_Mux(Word(i), Index, NiZ);  -- If NO, save its Index,
         W     := W_Mux(Ni,      W,     NiZ);  -- ... and save the Word.
      end loop;
 
      -- Set Index to be the bit-position of the lowest non-zero Word:
      Index := Shift_Left(Index, BitnessLog2); -- Index := Index * Bitness
 
      -- Handle degenerate case: if W is equal to 0, Index is not changed;
      -- Otherwise, start by advancing Index by an entire Word Bitness:
      Index := Index + ((0 - W_NZeroP(W)) and Word(Bitness));
 
      -- Now crank back the Index by the number of high bits of W (i.e.
      -- starting from its top) that must be discarded for W to become zero:
      for b in 1 .. Bitness loop
 
         -- If W is non-zero at this time, decrement the Index:
         Index := Index - W_NZeroP(W);
 
         -- Advance W left, i.e. discard the top bit of it:
         W     := Shift_Left(W, 1);
 
      end loop;
 
      -- If N = 0, result will be 0; otherwise: length of bottom zeros in N.
      return FZBit_Index(Index);
 
   end FZ_Count_Bottom_Zeros;
 
 
   -- Constant-Time Miller-Rabin Test on N using the given Witness.
   -- Witness will be used as-is if it conforms to the valid bounds,
   -- i.e. 2 < = Witness <= N - 2; otherwise will be transformed into a
   -- valid Witness via modular arithmetic.
   -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND.
   -- Handles degenerate cases of N that M-R per se cannot eat:
   -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'.
   -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.'
   -- For ALL other N, the output is equal to that of the M-R test.
   function FZ_MR_Composite_On_Witness(N       : in  FZ;
                                       Witness : in  FZ) return WBool is
 
      -- Widths of N, Witness, and Result are equal :
      subtype Width is Word_Index range N'Range;
 
      -- Whether N is 'small' (i.e. 1 Word) and therefore possibly degenerate :
      N_Is_Small       : constant WBool := FZ_OneWordP(N);
 
      -- Head of N, for detecting (and handling) the degenerate-N case :
      N_Head           : constant Word  := FZ_Get_Head(N);
 
      -- Zero and One are defined as COMPOSITE degenerate cases of N :
      N_Is_Zero_Or_One : constant WBool
        := N_Is_Small and (W_EqP(N_Head, 0) or W_EqP(N_Head, 1));
 
      -- Two and Three are PRIME degenerate cases of N :
      N_Is_Two         : constant WBool := N_Is_Small and W_EqP(N_Head, 2);
      N_Is_Three       : constant WBool := N_Is_Small and W_EqP(N_Head, 3);
 
      -- The COMPOSITE degenerate case of N where N != 2 and N is Even :
      N_Ne_2_Is_Even   : constant WBool :=
        (1 - N_Is_Two) and (1 - W_OddP(N_Head));
 
      -- Degeneracy latch. If N is Zero or One, then set immediately :
      Degen_Composite  : constant WBool := N_Is_Zero_Or_One or N_Ne_2_Is_Even;
 
      -- Possible-primality latch. If N is Two or Three, then set immediately :
      Possibly_Prime   : WBool := N_Is_Two or N_Is_Three;
 
      -- The writable copy of N that we will operate on :
      X                : FZ(Width) := N;
 
      -- Potentially-replaced head of X (if degenerate N) :
      X_Head           : Word := N_Head;
 
      -- Will be Barrettoid(X), for operations modulo X :
      XBar             : Barretoid(ZXMLength       => X'Length + 1,
                                   BarretoidLength => 2 * X'Length);
 
      -- The Bound Witness, constrained to valid range 2 < = BW <= X - 2 :
      BW               : FZ(Width);
 
      -- Head of BW, for detecting crossing of the lower bound :
      BW_Head          : Word;
 
      -- X - 1 (for M-R proper, and to constrain BW) :
      X_Minus_One      : FZ(Width);
 
      -- X - 1 = 2^R * K, with K odd :
      K                : FZ(Width);
      R                : FZBit_Index;
 
      -- Working register for all M-R modular operations :
      T                : FZ(Width);
 
      -- For subtraction where no underflow can happen, barring cosmic ray:
      NoCarry          : WZeroOrDie := 0;
 
   begin
 
      -- First: X, which will remain equal to N unless N is degenerate:
 
      -- If N is one of the two prohibited small primes (2,3) X will become 5:
      X_Head := W_Mux(A => X_Head, B => 5, Sel => Possibly_Prime);
 
      -- If one of the two prohibited small composites (0,1), or even, then 9:
      X_Head := W_Mux(A => X_Head, B => 9, Sel => Degen_Composite);
 
      -- Given as we're stuck carrying out M-R even if N is degenerate case,
      -- then let the M-R do The Right Thing, for added cosmic ray resistance.
 
      -- X gets a new head, if N was a degenerate case; else keeps old head:
      FZ_Set_Head(X, X_Head);
 
      -- Compute X - 1. As now X > 3, underflow is not permitted:
      FZ_Sub_W(X => X, W => 1, Difference => X_Minus_One,
               Underflow => NoCarry);
 
      -- Now, compute BW (Bound Witness), which satisfies 2 < = BW <= X - 2:
 
      -- First, BW := Witness mod (X - 1). After this, 0 <= BW <= X - 2:
      FZ_Mod(Dividend => Witness, Divisor => X_Minus_One, Remainder => BW);
 
      -- Now, adjust BW if it is found to be below Two (the lower bound) :
 
      -- Get head of BW:
      BW_Head := FZ_Get_Head(BW);
 
      -- If BW is equal to Zero or One, it will be forced to equal Two:
      BW_Head := W_Mux(A   => BW_Head,
                       B   => 2,
                       Sel => FZ_OneWordP(BW) and
                         (W_EqP(BW_Head, 0) or W_EqP(BW_Head, 1)));
 
      -- BW gets the new head, if it must; otherwise keeps its old head:
      FZ_Set_Head(BW, BW_Head);
 
      -- We finished adjusting X and BW for degeneracies, and can now M-R:
 
      -- Generate Barrettoid(X) to use in all of the modulo-X operations:
      FZ_Make_Barrettoid(Modulus => X, Result => XBar);
 
      -- Find R >= 1, and odd K, where X − 1 = 2^R * K :
 
      -- ... first, find R, the largest power of two which divides X - 1 :
      R := FZ_Count_Bottom_Zeros(X_Minus_One);
 
      -- ... and now obtain K := X / 2^R, i.e., K := X >> R :
      FZ_Quiet_ShiftRight(N => X_Minus_One, ShiftedN => K, Count => R);
 
      -- T := BW^K mod X
      FZ_Mod_Exp_Barrett(Base => BW, Exponent => K, Bar => XBar, Result => T);
 
      -- if T = 1 or T = X - 1, then X is possibly-prime:
      Possibly_Prime := Possibly_Prime or
        FZ_EqP_W(T, 1) or FZ_EqP(T, X_Minus_One);
 
      -- Needs R - 1 times, but perform for max possible count (gated):
      for i in 1 .. FZ_Bitness(N) - 1 loop
 
         -- T := T^2 mod X
         FZ_Mod_Sqr_Barrett(X => T, Bar => XBar, Product => T);
 
         -- if T = X - 1, and i < R, then X is possibly-prime:
         Possibly_Prime := Possibly_Prime or 
           (FZ_EqP(T, X_Minus_One) and W_LtP(Word(i), Word(R)));
 
      end loop;
 
      -- The output, which will be 1 iff X WAS FOUND to be composite via BW,
      -- ... or if X was found to equal Zero or One (without regard to BW.)
      return (1 - Possibly_Prime) or Degen_Composite;
      -- If X was found to equal Two or Three, output will be 0 (under any BW).
 
   end FZ_MR_Composite_On_Witness;
 
end FZ_Prime;

Observe that degenerate values of N result in a re-assignment, such that the M-R procedure (which is carried out regardless of degeneracy, for constant-time operation) is forced to arrive at a correct output, acting as "anti-cosmicray" backup to the degeneracy latches.


Now, let's run the program, and get an idea of how it works. Let's create a FFA Tape which executes M-R, via random witnesses, on the first 12 Mersenne Primes:

.2   .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.3   .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.5   .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.7   .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.d   .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.11  .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.13  .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.1f  .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.3d  .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.59  .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.6b  .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z
 
.7f  .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z

Now, run the tape as follows:

$ cat 12_mersenne.tape | ./bin/ffa_calc 256 3

... and if successful, the output will be:

MR(2^0000000000000000000000000000000000000000000000000000000000000002
- 1)=Prime
MR(2^0000000000000000000000000000000000000000000000000000000000000003
- 1)=Prime
MR(2^0000000000000000000000000000000000000000000000000000000000000005
- 1)=Prime
MR(2^0000000000000000000000000000000000000000000000000000000000000007
- 1)=Prime
MR(2^000000000000000000000000000000000000000000000000000000000000000D
- 1)=Prime
MR(2^0000000000000000000000000000000000000000000000000000000000000011
- 1)=Prime
MR(2^0000000000000000000000000000000000000000000000000000000000000013
- 1)=Prime
MR(2^000000000000000000000000000000000000000000000000000000000000001F
- 1)=Prime
MR(2^000000000000000000000000000000000000000000000000000000000000003D
- 1)=Prime
MR(2^0000000000000000000000000000000000000000000000000000000000000059
- 1)=Prime
MR(2^000000000000000000000000000000000000000000000000000000000000006B
- 1)=Prime
MR(2^000000000000000000000000000000000000000000000000000000000000007F
- 1)=Prime


M-R is, of course, not the optimal means of confirming the primality of a suspected Mersenne prime. But it does give us a basic test: regardless of the output of your RNG, you will always see the above output.

Let's now try a large number known to be prime, the 18th Mersenne prime, 23217 - 1:

.c91   .1`LS.1-?P[MR(2^]`#[- 1)=]{[Composite
]}{[Prime
]}Z

Run this tape as follows:

$ cat 18th_mersenne.tape | ./bin/ffa_calc 4096 3

... and the output will always be:

MR(2^
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000C91
- 1)=Prime


Now, let's test the M-R mechanism on more cryptographically-typical inputs. Let's take one of the braindamaged RSA moduli from the Phuctor zoo (the stars of the SecLab incident), and a Witness of 3:

.c08b0693f9ae0854829cd88d6538756df69ff8067d1556678f7e45b17437014374174c4
aca94bf1f83640928832b398f88c935c6a08177c4cbaa8b85002fee95068bd68487f286f
e3b814d92d6147b3d90fba606701f72e1f205c3e06dba55f5e180e45c2225a6ca2061d2d
638ef42609c5d8225620107519628b35983e92e0930ff2e2b8a3a0d9da57a4f50aaefe21
c0b02f8a91587f3ea2337df593f2faea40cb0d6359fee2df45b14b4e8f20988c542b81c7
862f74ea3a3761c22f6ecef64efb2014ccdcf13fb251ed3160ee20f392d0a2200db105c4
5bc12badbaa53a00a1371a77e12de455824c10dafd87f9c150f1e3fb622a8bb68134764a
77a939371bbe63ede53591d1b2bf35ff2f15776a2e1670c8c0006973782c52e97ded5ad1
e4cc96cc4bffd73061e14059aa40dbbc89d46ea1e20500a0e5ac7ac374c277e8d745dc45
449505d1c1bafecd9df8aa75096fffe4cd2f164e2a12d35000782dd73a5b58f8064ea4c0
afe2066f31d336fe65c50a9dff8e3db8a379b182e6d440cb8903fad5ed8477bde7ac2c13
1a7cd47d94630e92f98f68b86d6288607d1ef03880ca18f4176caf08869df93e93433a08
20af7e82e5eed7fd39a2480d98c34f5862dd7ceb4f8382a84acad97d1ee8da685d2e4aa5
f26167a3385f0a3412e168162916dd7ec1a864431f649e610d0ed2593d1be2abda31bb48
a66214a3f8e0ba011
.3
P
#

$ cat seclab_1.tape | ./bin/ffa_calc 4096 3

... and the output will be 1 (Composite), given as 3 is a M-R witness for that integer (which, like all other RSA moduli, is in fact composite.)

Let's now execute M-R on the shared factor of the two Seclab moduli, via a random witness:

.f59cc31339d001d37570dc0ccd986f3f5ea737fa9185c15dbc17e6bfef29435c79a7c22
e8616738947cab8711b6a6e7b5704e5283b57892adad3b170c726f34d3a9859b1504e005
ee4b69d4803cd56773c50ab01d6546ce66dcdb2be4a34e15160d8e0eb69184b699246b42
28f6f25bfcc91970fa99ea3123409f6865b161423581a5f9522ef774f09818bfef6c2b1c
51d06218a07dc717ec94bb231b062936bfd8794cb39bdf8dc05cd2c8bd74b1d0acb14d39
bc293deb45fa52de89af30e4bc5688fb8116be7e7ad4332810c04903939ee2a356ea254b
83fb811c76898672d24997d8647f969a8e02aa2f2016cb1e0c8a9afe99760cd37bf2794d
4ea58951f
?
P
#

$ cat seclab_gcd.tape | ./bin/ffa_calc 2048 3

Do this as many times as you care to (in the next Chapter, we will discuss exactly what is gained from repeatedly invoking M-R on randomly-generated Witnesses) and the output will remain 0 (i.e. Probably-Prime. I personally gave it 40 shots, and have not found a witness of compositivity for it. At this point I would bet money that it is in fact prime -- but there is no way to settle the bet, as AFAIK there does not presently exist a deterministic primality test that will operate on numbers of this length reasonably quickly.)


Now, let's exhibit the reason why our M-R test is formulated in such a way that the operator is free to specify an arbitrary valid M-R Witness, rather than the nonsense seen in heathen arithmetrons, where the witness is either drawn from a set of fixed values, or taken directly from RNG.

The reason for this is so that the operator is able to confirm, at arbitrary times and with arbitrary values of his choosing, that the M-R mechanism actually performs M-R and not something else.

Let's perform M-R on the smallest composite integer where 2, 3, 5, 7 are "Liars", i.e. do not function as M-R Witnesses: 3215031751 (equal to 151 × 751 × 28351) :

.bfa17dc7 .2 P #
.bfa17dc7 .3 P #
.bfa17dc7 .5 P #
.bfa17dc7 .7 P #

$ cat liars.tape | ./bin/ffa_calc 256 3

Produces:

0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

However we know that 11 is a M-R Witness for 3215031751:

.bfa17dc7 .B P #

0000000000000000000000000000000000000000000000000000000000000001

We thereby confirm that the given program in fact behaves as M-R, for the given audit input. You will want to generate your own audit tape if using FFA in anger, for this as well as other commands.


In Chapter 16B, we will demonstrate a proof that the supplied algorithm is in fact a Monte Carlo Primality Test, and discuss the statistical facts governing its proper use. We will also discuss the CPU cost of the algorithm, as a function of FFA Bitness.

In Chapter 17, we will... but let's not spoil it!


~To be continued!~

// Script to allow anchoring of user-selected content on html pages. // Original idea deployed by http://archive.today // Packaged for WordPress on http://trilema.com/2015/that-spiffy-selection-thing/