Primes / Blum Primes

[Charles Pegge]

The first 1000 primes:

Code Select Expand

uses console

============
class Primes
============
'
int nn 'array elements
sys p 'array buffer address
'
method constructor(int n)
=========================
'generate primes
int i,j,k,t
t=n
redim quad q(t+1)
quad r
quad m=1
indexbase 0
nn=n
i=0
while i<t
  k=1
  for j=2 to i-1
    r=mod(m,q[j])
    if r=0
      k=0
      exit for
    endif
  next
  if k
    i++
    q[i]=m
  endif
  m++
wend
nn=n
p=@q
end method
'
method get(int i) as quad
if i<1 or i>nn
  exit method
endif
quad q at (i*8+p)
return q
end method
'
end class 'Primes
'
'TEST
=====
new Primes P(1000)
int i
for i=1 to P.nn
  print i tab P.get(i) cr
next
del P
wait


Blum Primes are primes with modulus 4 = 3. That means: (PrimeNum and 3)=3.

Code Select Expand

uses console

================
class BlumPrimes
================
'
int nn 'array elements
sys p 'array buffer address
'
method constructor(int n)
=========================
'generate primes
int i,j,k,t
t=n*2
redim quad q(t+1)
quad r
quad m=1
indexbase 0
nn=n
i=0
while i<t
  k=1
  for j=2 to i-1
    r=mod(m,q[j])
    if r=0
      k=0
      exit for
    endif
  next
  if k
    i++
    q[i]=m
  endif
  m++
wend
'filter for Blum primes
j=0
for i=1 to t
  k=q[i] 'clipped to 32bits
  if (k and 3) = 3 'quick modulo 4
    j++
    q[j]=q[i]
    if j>=nn
      exit for
    endif
  endif
next
nn=j
'print i cr
p=@q
end method
'
method get(int i) as quad
if i<1 or i>nn
  exit method
endif
quad q at (i*8+p)
return q
end method
'
end class 'BlumPrimes
'
'TEST
=====
new BlumPrimes BP(1000)
int i
for i=1 to BP.nn
  print i tab BP.get(i) cr
next
del BP
wait


[Charles Pegge]

With some assistance from Bing Copilot:

Code Select Expand

'BlumBlumShub Randomizer
uses console

================
class BlumPrimes
================
'
int nn 'array elements
sys p 'array buffer address
'
method constructor(int n)
=========================
'generate primes
int i,j,k,t
t=n*2
redim quad q(t+1)
quad r
quad m=1
indexbase 0
nn=n
i=0
while i<t
  k=1
  for j=2 to i-1
    r=mod(m,q[j])
    if r=0
      k=0
      exit for
    endif
  next
  if k
    i++
    q[i]=m
  endif
  m++
wend
'filter for Blum primes
j=0
for i=1 to t
  k=q[i] 'clipped to 32bits
  if (k and 3) = 3 'quick modulo 4
    j++
    q[j]=q[i]
    if j>=nn
      exit for
    endif
  endif
next
nn=j
print i cr
p=@q
end method
'
method get(int i) as quad
if i<1 or i>nn
  exit method
endif
quad q at (i*8+p)
return q
end method
'
end class 'BlumPrimes
'
'TEST
'new BlumPrimes BP(1000)
'int i
'for i=1 to BP.nn
'  print i tab BP.get(i) cr
'next
'del BP
'wait


==================
class BlumBlumShub
==================
'
quad P,Q,N,state
'
method constructor(dword iP, iQ, iseed)
  'P(P), Q(Q), N(P * Q), state(seed) {}
  P=iP
  Q=iQ
  N=iP*iQ
  state=iseed
end method

method get() as quad
  'state = mod(state * state,N)
  state = (state * state) mod N
  return state
end method

method getBit() as int
  return mod(get(), 2)
end method

end class 'BlumBlumShub

  'TEST
  =====
  ' Choose large Blum prime numbers P and Q
  ' Blum prime numbers (where P ≡ 3 (mod 4))
  quad P = 17159 '11
  quad Q = 17167 '23
  quad seed = 1234
  new BlumBlumShub brnd(P, Q, seed)
  '
  ' Generate a sequence of random numbers
  int i
  for i=0 to 19
    print i tab " " brnd.get() cr
  next
  '
  wait
  del brnd


[Theo Gottwald]

The given code consists of two classes: `BlumPrimes` and `BlumBlumShub`. The `BlumPrimes` class generates Blum primes and stores them in an array. The `BlumBlumShub` class is a pseudorandom number generator that uses two large Blum prime numbers P and Q to generate a sequence of random numbers.

Here's an optimized version of the code in x86 ASM using the System V AMD64 ABI:

```assembly

Code Select Expand

section .data
    ; Test data
    P dq 17159
    Q dq 17167
    seed dq 1234
    fmt db "%d: %lu", 10, 0

section .bss
    ; BlumBlumShub object
    state resq 1
    N resq 1

section .text
    global main
    extern printf

; Function to check if a number is a Blum prime (returns 1 if true, 0 otherwise)
; Input: RDI (number to check)
; Output: RAX (1 if Blum prime, 0 otherwise)
is_blum_prime:
    push rbp
    mov rbp, rsp

    ; Check if the number is prime
    ; ... (Implement a prime checking algorithm like Miller-Rabin or trial division)

    ; Check if the number is congruent to 3 modulo 4
    mov rax, rdi
    and rax, 3
    cmp rax, 3
    jne .not_blum_prime

    mov rax, 1 ; The number is a Blum prime
    jmp .end

.not_blum_prime:
    xor rax, rax ; The number is not a Blum prime

.end:
    leave
    ret

; BlumBlumShub constructor
; Input: RDI (P), RSI (Q), RDX (seed)
; Output: None
blum_blum_shub_constructor:
    push rbp
    mov rbp, rsp

    mov rax, [rdi] ; Load P
    imul rsi ; Multiply by Q
    mov [N], rax ; Store N

    mov rax, [rdx] ; Load seed
    mov [state], rax ; Store state

    leave
    ret

; BlumBlumShub get method
; Input: None
; Output: RAX (random number)
blum_blum_shub_get:
    push rbp
    mov rbp, rsp

    mov rax, [state] ; Load state
    imul rax ; Square state
    mov rdx, 0 ; Clear RDX for division
    div qword [N] ; Divide by N (remainder in RDX)
    mov [state], rdx ; Store new state

    mov rax, rdx ; Return the remainder as the random number
    leave
    ret

; BlumBlumShub getBit method
; Input: None
; Output: RAX (0 or 1)
blum_blum_shub_get_bit:
    push rbp
    mov rbp, rsp

    call blum_blum_shub_get ; Get random number
    and rax, 1 ; Get least significant bit

    leave
    ret

main:
    ; Initialize BlumBlumShub
    mov rdi, [P]
    mov rsi, [Q]
    lea rdx, [seed]
    call blum_blum_shub_constructor

    ; Generate a sequence of random numbers
    xor ecx, ecx ; Counter
.loop:
    cmp ecx, 20
    jge .end_loop

    ; Print the index and random number
    mov rdi, fmt
    mov rsi, ecx
    call blum_blum_shub_get
    mov rdx, rax
    xor rax, rax
    call printf

    inc ecx
    jmp .loop

.end_loop:
    ; Exit
    xor eax, eax
    ret
```
This x86 ASM code attempts to optimize the given code by using efficient arithmetic operations and following the System V AMD64 ABI for function calls. It uses the `is_blum_prime` function to check if a number is a Blum prime, which can be implemented using a prime checking algorithm like Miller-Rabin or trial division. The `blum_blum_shub_constructor`, `blum_blum_shub_get`, and `blum_blum_shub_get_bit` functions implement the BlumBlumShub pseudorandom number generator.

Using MiSTRAL AI

Here a second shot:

Here's a simple implementation of a trial division prime checking algorithm in x86 ASM:

```assembly

Code Select Expand

; Function to check if a number is prime using trial division
; Input: RDI (number to check)
; Output: RAX (1 if prime, 0 otherwise)
is_prime:
    push rbp
    mov rbp, rsp

    cmp rdi, 2 ; Check if the number is less than 2
    jl .not_prime

    cmp rdi, 3 ; Check if the number is 3
    je .prime

    mov rax, rdi
    and rax, 1 ; Check if the number is even
    jz .not_prime

    mov rax, 3 ; Start checking divisibility from 3
.check_divisibility:
    cmp rax, rdi
    jge .prime ; If we've reached the number itself, it's prime

    mov rdx, 0
    div rax ; Divide the number by the current divisor
    cmp rdx, 0 ; Check if there's a remainder
    jz .not_prime ; If there's no remainder, the number is not prime

    add rax, 2 ; Increment the divisor by 2 (only check odd divisors)
    jmp .check_divisibility

.prime:
    mov rax, 1 ; The number is prime
    jmp .end

.not_prime:
    xor rax, rax ; The number is not prime

.end:
    leave
    ret
```
This function checks if a number is prime by trying to divide it by all odd numbers up to its square root (since a larger factor of the number would have already been tried as a smaller factor of another number). If none of the divisors divide the number evenly, then the number is prime.

To use this prime checking algorithm in the `is_blum_prime` function, replace the comment `; Check if the number is prime` with a call to `is_prime`:

```assembly

Code Select Expand

; Function to check if a number is a Blum prime (returns 1 if true, 0 otherwise)
; Input: RDI (number to check)
; Output: RAX (1 if Blum prime, 0 otherwise)
is_blum_prime:
    push rbp
    mov rbp, rsp

    ; Check if the number is prime
    call is_prime
    cmp rax, 0
    je .not_blum_prime

    ; Check if the number is congruent to 3 modulo 4
    mov rax, rdi
    and rax, 3
    cmp rax, 3
    jne .not_blum_prime

    mov rax, 1 ; The number is a Blum prime
    jmp .end

.not_blum_prime:
    xor rax, rax ; The number is not a Blum prime

.end:
    leave
    ret
```


[Charles Pegge]

Definitely worth optimizing these algorithms, but the problem inherent in BlumBlumShub is the requirement for division to calculate the modulus. Division is always computationally expensive, requiring hardware iteration. So BlumBlumShub would not be the best choice for high-speed use, for instance generating large texture maps.