larger number calculations with positive integers

Share your advanced PureBasic knowledge/code with the community.
User avatar
pcfreak
User
User
Posts: 75
Joined: Sat May 22, 2004 1:38 am

larger number calculations with positive integers

Post by pcfreak »

At first I started coding this because I wanted to do RSA in PureBasic and couldn't get the GMP library
compiled in a way it doesn't needs a dll in Windows and works with PureBasic. I'm still not able to compile
the GMP Library that way with MinGW but I don't have the time anymore to play with such things.
Maybe someone else wants to make use of the functions I already wrote. Anyway, here are some
procedures to make calculations with large numbers in PureBasic x86 but only with positive integers.
If anyone improves this or makes extensions I'd be glad if it could be shared here, too.
As for this code here it's free to use and modify.

Have fun with it. :)

BigNumbers.pbi

Code: Select all

;Internal ASM Macros (don't change)
!macro BNPV_PUSH [register]
!{
! BNPV_VARC = 0
! if ~ defined BNPV_OFFSET
!  BNPV_OFFSET = 0
! end if
! if ~ register eq
!  PUSH register
!  BNPV_OFFSET = BNPV_OFFSET+4
! end if
!}
!macro BNPV_POP [register]
!{
! if ~ register eq
!  reverse POP register
!  BNPV_OFFSET = 0
! end if
!}
!macro BNPV_VARS [varName]
!{
! common
!  BNPV_VARC = -4
! forward
!  BNPV_VARC = BNPV_VARC+4
!  BNPV_OFFSET = BNPV_OFFSET+4
!  if ~ varName eq
!   local varOffset
!   varOffset = BNPV_VARC
!   varName equ esp+varOffset
!   PUSH 0 
!  end if
!}
!macro BNPV_FREEVARS
!{
! if BNPV_VARC <> -4
!  ADD esp, BNPV_VARC+4
!  BNPV_OFFSET = BNPV_OFFSET-(BNPV_VARC+4)
! end if
!}

Macro _bn_qt()
 "
EndMacro



;MAIN_MACRO
;
; - contains all functions
; - call with or without special naming
;   -> names will be added to the size constant, the structure name and behind the BN of every function
; - disable check weather 0 was passed as memory pointer or not (little speed increase, but not always)
; - compile optimized for size rather than speed or leave it default

Macro InitBigNumbers(_bn_bits, _bn_naming=, _bn_checkmem=#True, _bn_size_optimized=#False) ;_bn_bits must be a multiple of 32
#BIG_NUMBER#_bn_naming#_LONGS = _bn_bits/32
!BIG_NUMBER#_bn_naming#_LONGS = _bn_bits/32

Structure BIG_NUMBER#_bn_naming#
 n.l[#BIG_NUMBER#_bn_naming#_LONGS]
EndStructure


Declare.l BN#_bn_naming#_INT(*dest.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_VAL(*dest.BIG_NUMBER#_bn_naming#, a.s)
Declare.s BN#_bn_naming#_STR(*a.BIG_NUMBER#_bn_naming#)
Declare.s BN#_bn_naming#_HEX(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_ADD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_ADDINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_SUB(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_SUBINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_MUL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, dwordsA.l = -1, dwordsB.l = -1)
Declare.l BN#_bn_naming#_KARATSUBA(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_MULINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_POW(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_POWINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_POW_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *m.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_POW_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, m.l)
Declare.l BN#_bn_naming#_SQR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_DIV(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_DIVINT(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_GCD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_INV_MOD(*dest.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *n.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_RND(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_RND_MAX(*dest.BIG_NUMBER#_bn_naming#, bits.l)
Declare.l BN#_bn_naming#_MOV(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_NOT(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_AND(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_OR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_XOR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_SHL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_SHL1(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_SHR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_SHR1(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_CMP(*a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_CMPINT(*a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_IS_EVEN(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_IS_PRIME(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_NEXT_PRIME(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_USED_BITS(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_USED_LONGS(*a.BIG_NUMBER#_bn_naming#)


;- BN_INT(*dest.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_INT(*dest.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *dest=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !XOR eax, eax
 CompilerIf _bn_size_optimized
 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
  !@@:
   !MOV dword [edi+ecx*4], eax
   !DEC ecx
  !JNZ @b
 !end if
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS-1
  !MOV dword [edi+(%)*4], eax
 !end repeat
 CompilerEndIf
 !MOV eax, dword [p.v_b+BNPV_OFFSET]
 !MOV dword [edi], eax
 !BNPV_POP esi,edi
 ProcedureReturn *dest
EndProcedure

;- BN_VAL(*dest.BIG_NUMBER, a.s)
Procedure.l BN#_bn_naming#_VAL(*dest.BIG_NUMBER#_bn_naming#, a.s)
 Protected *tmp.BIG_NUMBER#_bn_naming#, *char.CHARACTER
 CompilerIf _bn_checkmem=#True
 If *dest=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 *tmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#))
 If *tmp=0
  ProcedureReturn 0
 EndIf
 !MOV edx, dword [p.p_dest+BNPV_OFFSET]
 !XOR eax, eax
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV dword [edx+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV dword [edx+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 *char = @a
 While *char\c
  If *char\c >= '0' And *char\c <= '9'
   If *char <> @a
    BN#_bn_naming#_MULINT(*tmp, *dest, 10)
   EndIf
   BN#_bn_naming#_ADDINT(*dest, *tmp, *char\c - '0')
  EndIf
  *char + 1 + #PB_Compiler_Unicode
 Wend
 FreeMemory(*tmp)
 ProcedureReturn *dest
EndProcedure

;- BN_STR(*a.BIG_NUMBER)
Procedure.s BN#_bn_naming#_STR(*a.BIG_NUMBER#_bn_naming#)
 Protected *div.BIG_NUMBER#_bn_naming#, *mod.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, Buf$, i.l
 CompilerIf _bn_checkmem=#True
 If *a=0
  ProcedureReturn ""
 EndIf
 CompilerEndIf
 *div = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
 *mod = *div+SizeOf(BIG_NUMBER#_bn_naming#)
 *tmp = *mod+SizeOf(BIG_NUMBER#_bn_naming#)
 If *div=0
  ProcedureReturn ""
 EndIf
 BN#_bn_naming#_MOV(*tmp, *a)
 Repeat
  BN#_bn_naming#_DIVINT(*div, *mod, *tmp, 10)
  Buf$ = Str(*mod\n[0] & $F) + Buf$
  BN#_bn_naming#_MOV(*tmp, *div)
 Until BN#_bn_naming#_CMPINT(*div, 0) = 0
 FreeMemory(*div)
 ProcedureReturn Buf$
EndProcedure

;- BN_HEX(*a.BIG_NUMBER)
Procedure.s BN#_bn_naming#_HEX(*a.BIG_NUMBER#_bn_naming#)
 Protected Buf$, i.l
 CompilerIf _bn_checkmem=#True
 If *a=0
  ProcedureReturn ""
 EndIf
 CompilerEndIf
 For i=#BIG_NUMBER#_bn_naming#_LONGS-1 To 0 Step -1
  Buf$ + RSet(Hex(*a\n[i] & $FFFFFFFF),8,"0")
 Next
 ProcedureReturn Buf$
EndProcedure

;- BN_ADD(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_ADD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV ecx, dword [p.p_b+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !MOV eax, dword [esi]
 !ADD eax, dword [ecx]
 !MOV dword [edi], eax
 CompilerIf _bn_size_optimized
 !MOV edx, 1
 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !PUSHFD
  !@@:
   !POPFD
   !MOV eax, dword [esi+edx*4]
   !ADC eax, dword [ecx+edx*4]
   !MOV dword [edi+edx*4], eax
   !PUSHFD
   !INC edx
   !CMP edx, BIG_NUMBER#_bn_naming#_LONGS
  !JB @b
  !POPFD
 !end if
 CompilerElse
 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !repeat BIG_NUMBER#_bn_naming#_LONGS-1
   !MOV eax, dword [esi+%*4]
   !ADC eax, dword [ecx+%*4]
   !MOV dword [edi+%*4], eax
  !end repeat
 !end if
 CompilerEndIf
 !BNPV_POP esi,edi
 CompilerIf #PB_Compiler_Debugger
 !JNC @f
 Debug _bn_qt()BN#_bn_naming#_ADD Overflow#_bn_qt()
 !@@:
 CompilerEndIf
 ProcedureReturn *dest
EndProcedure

;- BN_ADDINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_ADDInt(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !MOV eax, dword [esi]
 !ADD eax, dword [p.v_b+BNPV_OFFSET]
 !MOV dword [edi], eax
 !JNC @@BN#_bn_naming#_ADDINT_procend
 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !repeat BIG_NUMBER#_bn_naming#_LONGS-1
   !MOV eax, dword [esi+%*4]
   !ADC eax, 0
   !MOV dword [edi+%*4], eax
   !if % < BIG_NUMBER#_bn_naming#_LONGS-1
    !JNC @@BN#_bn_naming#_ADDINT_procend
   !end if
  !end repeat
 !end if
 !JMP @@BN#_bn_naming#_ADDINT_procend2
 !@@BN#_bn_naming#_ADDINT_procend:
  !if BIG_NUMBER#_bn_naming#_LONGS > 1
   !repeat BIG_NUMBER#_bn_naming#_LONGS-1
    !MOV eax, dword [esi+%*4]
    !MOV dword [edi+%*4], eax
   !end repeat
  !end if
 !@@BN#_bn_naming#_ADDINT_procend2:
 !BNPV_POP esi,edi
 CompilerIf #PB_Compiler_Debugger
 !JNC @f
 Debug _bn_qt()BN#_bn_naming#_ADDINT Overflow#_bn_qt()
 !@@:
 CompilerEndIf
 ProcedureReturn *dest
EndProcedure

;- BN_SUB(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SUB(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV ecx, dword [p.p_b+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !MOV eax, dword [esi]
 !SUB eax, dword [ecx]
 !MOV dword [edi], eax
 CompilerIf _bn_size_optimized
 !MOV edx, 1
 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !PUSHFD
  !@@:
   !POPFD
   !MOV eax, dword [esi+edx*4]
   !SBB eax, dword [ecx+edx*4]
   !MOV dword [edi+edx*4], eax
   !PUSHFD
   !INC edx
   !CMP edx, BIG_NUMBER#_bn_naming#_LONGS
  !JB @b
  !POPFD
 !end if
 CompilerElse
 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !repeat BIG_NUMBER#_bn_naming#_LONGS-1
   !MOV eax, dword [esi+%*4]
   !SBB eax, dword [ecx+%*4]
   !MOV dword [edi+%*4], eax
  !end repeat
 !end if
 CompilerEndIf
 !BNPV_POP esi,edi
 CompilerIf #PB_Compiler_Debugger
 !JNC @f
 Debug _bn_qt()BN#_bn_naming#_SUB Underflow#_bn_qt()
 !@@:
 CompilerEndIf
 ProcedureReturn *dest
EndProcedure

;- BN_SUBINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_SUBINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !MOV eax, dword [esi]
 !SUB eax, dword [p.v_b+BNPV_OFFSET]
 !JNC @@BN#_bn_naming#_SUBINT_procend

 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !MOV ecx, 1
  !@@BN#_bn_naming#_SUBINT_for1:
   !DEC ecx
   !MOV dword [edi+ecx*4], eax
   !INC ecx
   !MOV eax, dword [esi+ecx*4]
   !SUB eax, 1
   !JNC @@BN#_bn_naming#_SUBINT_copyRem
   !INC ecx
   !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
  !JB @@BN#_bn_naming#_SUBINT_for1
  !@@BN#_bn_naming#_SUBINT_next1:
  !JMP @@BN#_bn_naming#_SUBINT_endCopyRem
  !@@BN#_bn_naming#_SUBINT_copyRem:
  !MOV dword [edi+ecx*4], eax
  !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
  !JB @@BN#_bn_naming#_SUBINT_endCopyRem
  !@@:
   !MOV eax, dword [esi+ecx*4]
   !MOV dword [edi+ecx*4], eax
   !INC ecx
   !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
  !JB @b
  !@@BN#_bn_naming#_SUBINT_endCopyRem:
 !end if

 !BNPV_POP esi,edi
 ProcedureReturn *dest
 !@@BN#_bn_naming#_SUBINT_procend:
 !MOV dword [edi], eax
 !if BIG_NUMBER#_bn_naming#_LONGS > 1
  !repeat BIG_NUMBER#_bn_naming#_LONGS-1
   !MOV eax, dword [esi+%*4]
   !MOV dword [edi+%*4], eax
  !end repeat
 !end if
 !BNPV_POP esi,edi
 ProcedureReturn *dest
EndProcedure


;____________________
;           9   9   9
;           9   9   9
;=-------------------
;          81  81  81
;      81  81  81    
;+ 81  81  81        
;=-------------------
;  81 162 243 162  81
;= 99   8   0   0   1
;____________________
;____________________
;
;           1   2   3
;           6   5   4
;=-------------------
;           4   8  12
;       5  10  15    
;+  6  12  18        
;=-------------------
;   6  17  32  23  12
;=  8   0   4   4   2
;____________________
;- BN_MUL(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
;- TODO: try Karatsuba algorithm or Schoenhage-Strassen-Algorithm if possible
Procedure.l BN#_bn_naming#_MUL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, dwordsA.l = -1, dwordsB.l = -1)
;  Protected dwordsA.l, dwordsB.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 If dwordsA < 0
  dwordsA = BN#_bn_naming#_USED_LONGS(*a)
 EndIf
 If dwordsB < 0
  dwordsB = BN#_bn_naming#_USED_LONGS(*b)
 EndIf
 If dwordsA<dwordsB
  Swap dwordsA, dwordsB
  Swap *a, *b
 EndIf
 !BNPV_PUSH ebx,esi,edi,ebp
 !BNPV_VARS p.v_iA, p.v_iB
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV ebp, dword [p.p_b+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !XOR eax, eax
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 !CMP dword [p.v_dwordsA+BNPV_OFFSET], 0
 !JBE @@BN#_bn_naming#_MUL_next1
 !CMP dword [p.v_dwordsB+BNPV_OFFSET], 0
 !JBE @@BN#_bn_naming#_MUL_next1
 !@@BN#_bn_naming#_MUL_for1:
  !MOV dword [p.v_iA], 0
  !@@BN#_bn_naming#_MUL_for2:
   !MOV ecx, dword [p.v_iA]
   !ADD ecx, dword [p.v_iB] ;ecx = iA+iB
   !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
   !JAE @@BN#_bn_naming#_MUL_endif1
    !MOV edx, dword [p.v_iB]
    !MOV eax, dword [ebp+edx*4]
    !MOV ebx, dword [p.v_iA]
    !MUL dword [esi+ebx*4]
    !ADD dword [edi+ecx*4], eax
    !LAHF
    !INC ecx
    !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
    !JAE @@BN#_bn_naming#_MUL_else2
     !SAHF
     !ADC dword [edi+ecx*4], edx
     !JNC @@BN#_bn_naming#_MUL_endif2
     !LAHF
     !INC ecx
     !@@:
      !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
      !JAE @f
      !SAHF
      !ADC dword [edi+ecx*4], 0
      !LAHF
      !INC ecx
     !JC @b
     !@@:
     !SAHF
     !JC @@BN#_bn_naming#_MUL_overflow
     !JMP @@BN#_bn_naming#_MUL_endif2
    !@@BN#_bn_naming#_MUL_else2:
     !SAHF
     !JC @@BN#_bn_naming#_MUL_overflow
    !@@BN#_bn_naming#_MUL_endif2:
   !@@BN#_bn_naming#_MUL_endif1:
   !INC dword [p.v_iA]
   !MOV eax, dword [p.v_iA]
   !CMP dword [p.v_dwordsA+BNPV_OFFSET], eax
  !JA @@BN#_bn_naming#_MUL_for2
  !@@BN#_bn_naming#_MUL_next2:
  !INC dword [p.v_iB]
  !MOV eax, dword [p.v_iB]
  !CMP dword [p.v_dwordsB+BNPV_OFFSET], eax
 !JA @@BN#_bn_naming#_MUL_for1
 !@@BN#_bn_naming#_MUL_next1:
 !BNPV_FREEVARS
 !BNPV_POP ebx,esi,edi,ebp
 ProcedureReturn *dest
 !@@BN#_bn_naming#_MUL_overflow:
 !BNPV_FREEVARS
 !BNPV_POP ebx,esi,edi,ebp
 Debug _bn_qt()BN#_bn_naming#_MUL Overflow#_bn_qt()
 ProcedureReturn 0
EndProcedure

;- BN_KARATSUBA(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
;- TODO: rewrite optimized in asm
Procedure.l BN#_bn_naming#_KARATSUBA(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 Protected *xH.BIG_NUMBER#_bn_naming#, *xL.BIG_NUMBER#_bn_naming#, *yH.BIG_NUMBER#_bn_naming#, *hL.BIG_NUMBER#_bn_naming#
 Protected *P1.BIG_NUMBER#_bn_naming#, *P2.BIG_NUMBER#_bn_naming#, *P3.BIG_NUMBER#_bn_naming#
 Protected dwordsA.l, dwordsB.l, n.l;, range.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 dwordsA = BN#_bn_naming#_USED_LONGS(*a)
 dwordsB = BN#_bn_naming#_USED_LONGS(*b)
 If dwordsA < dwordsB
  n = dwordsB
 Else
  n = dwordsA
 EndIf
 range = Log(Sqr(#BIG_NUMBER#_bn_naming#_LONGS)) / Log(3)
 If n <= #BIG_NUMBER#_bn_naming#_LONGS >> range Or n < 18
  *dest = BN#_bn_naming#_MUL(*dest, *a, *b, dwordsA, dwordsB)
 ElseIf n * 2 <= #BIG_NUMBER#_bn_naming#_LONGS
  *xH = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#) * 7)
  *xL = *xH + SizeOf(BIG_NUMBER#_bn_naming#)
  *yH = *xL + SizeOf(BIG_NUMBER#_bn_naming#)
  *yL = *yH + SizeOf(BIG_NUMBER#_bn_naming#)
  *P1 = *yL + SizeOf(BIG_NUMBER#_bn_naming#)
  *P2 = *P1 + SizeOf(BIG_NUMBER#_bn_naming#)
  *P3 = *P2 + SizeOf(BIG_NUMBER#_bn_naming#)
  If *xH = 0
   ProcedureReturn 0
  EndIf
  n = n / 2
  !BNPV_PUSH esi,edi
  !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
  !@@BN#_bn_naming#_KARATSUBA_for1:
   !CMP ecx, dword [p.v_n+BNPV_OFFSET]
   !JB @f
    !MOV edx, ecx
    !SUB edx, dword [p.v_n+BNPV_OFFSET]
    !MOV esi, dword [p.p_a+BNPV_OFFSET]
    !MOV edi, dword [p.p_xH+BNPV_OFFSET]
    !MOV eax, dword [esi+ecx*4]
    !MOV dword [edi+edx*4], eax
    !MOV esi, dword [p.p_b+BNPV_OFFSET]
    !MOV edi, dword [p.p_yH+BNPV_OFFSET]
    !MOV eax, dword [esi+ecx*4]
    !MOV dword [edi+edx*4], eax
   !@@:
   !CMP ecx, dword [p.v_n+BNPV_OFFSET]
   !JAE @f
    !MOV esi, dword [p.p_a+BNPV_OFFSET]
    !MOV edi, dword [p.p_xL+BNPV_OFFSET]
    !MOV eax, dword [esi+ecx*4]
    !MOV dword [edi+ecx*4], eax
    !MOV esi, dword [p.p_b+BNPV_OFFSET]
    !MOV edi, dword [p.p_yL+BNPV_OFFSET]
    !MOV eax, dword [esi+ecx*4]
    !MOV dword [edi+ecx*4], eax
   !@@:
   !DEC ecx
  !JNS @@BN#_bn_naming#_KARATSUBA_for1
  !BNPV_POP esi,edi
  BN#_bn_naming#_KARATSUBA(*P1, *xH, *yH)
  BN#_bn_naming#_KARATSUBA(*P2, *xL, *yL)
  BN#_bn_naming#_ADD(*xL, *xL, *xH)
  BN#_bn_naming#_ADD(*yL, *yL, *yH)
  BN#_bn_naming#_KARATSUBA(*P3, *xL, *yL)
  BN#_bn_naming#_SHL(*xH, *P1, 2 * n * 32)
  BN#_bn_naming#_SUB(*xL, *P3, *P1) ;*
  BN#_bn_naming#_SUB(*P3, *xL, *P2)
  BN#_bn_naming#_SHL(*xL, *P3, n * 32)
  BN#_bn_naming#_ADD(*P1, *xH, *xL) ;*
  BN#_bn_naming#_ADD(*dest, *P1, *P2)
  FreeMemory(*xH)
 Else
  *dest = 0
  Debug _bn_qt()BN#_bn_naming#_KARATSUBA Overflow#_bn_qt()
 EndIf
 ProcedureReturn *dest
EndProcedure

;- BN_MULINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_MULINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 Protected dwordsA.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 dwordsA = BN#_bn_naming#_USED_LONGS(*a)
 !BNPV_PUSH ebx,esi,edi
 !BNPV_VARS p.v_iA
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !XOR eax, eax
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 !CMP dword [p.v_b+BNPV_OFFSET], 0
 !JBE @@BN#_bn_naming#_MULINT_endif0
 !CMP dword [p.v_dwordsA+BNPV_OFFSET], 0
 !JE @@BN#_bn_naming#_MULINT_endif0
  !MOV dword [p.v_iA], 0
  !@@BN#_bn_naming#_MULINT_for1:
   !MOV ecx, dword [p.v_iA] ;ecx = iA
   !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
   !JAE @@BN#_bn_naming#_MULINT_endif1
    !MOV eax, dword [p.v_b+BNPV_OFFSET]
    !MOV ebx, dword [p.v_iA]
    !MUL dword [esi+ebx*4]
    !ADD dword [edi+ecx*4], eax
    !LAHF
    !INC ecx
    !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
    !JAE @@BN#_bn_naming#_MULINT_else2
     !SAHF
     !ADC dword [edi+ecx*4], edx
     !JNC @@BN#_bn_naming#_MULINT_endif2
     !LAHF
     !INC ecx
     !@@:
      !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
      !JAE @f
      !SAHF
      !ADC dword [edi+ecx*4], 0
      !LAHF
      !INC ecx
     !JC @b
     !@@:
     !SAHF
     !JC @@BN#_bn_naming#_MULINT_overflow
     !JMP @@BN#_bn_naming#_MULINT_endif2
    !@@BN#_bn_naming#_MULINT_else2:
     !SAHF
     !JC @@BN#_bn_naming#_MULINT_overflow
    !@@BN#_bn_naming#_MULINT_endif2:
   !@@BN#_bn_naming#_MULINT_endif1:
   !INC dword [p.v_iA]
   !MOV eax, dword [p.v_iA]
   !CMP dword [p.v_dwordsA+BNPV_OFFSET], eax
  !JA @@BN#_bn_naming#_MULINT_for1
  !@@BN#_bn_naming#_MULINT_next2:
 !@@BN#_bn_naming#_MULINT_endif0:
 !BNPV_FREEVARS
 !BNPV_POP ebx,esi,edi
 ProcedureReturn *dest
 !@@BN#_bn_naming#_MULINT_overflow:
 !BNPV_FREEVARS
 !BNPV_POP ebx,esi,edi
 Debug _bn_qt()BN#_bn_naming#_MULINT Overflow#_bn_qt()
 ProcedureReturn 0
EndProcedure

; base.l = 7
; exp.l = 13
; 
; seed.l = exp
; result.q = 1
; tmp.q = base
; While seed>0
;  Debug Bin(seed)
;  If seed&1
;   result*tmp
;  EndIf
;  tmp*tmp
;  seed>>1
; Wend
; 
; Debug Str(base)+"^"+Str(exp)+" = "+StrU(result,4)
;96889010407
;- BN_POW(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_POW(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 Protected *seed.BIG_NUMBER#_bn_naming#, *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, bits.l, i.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 BN#_bn_naming#_INT(*dest, 0)
 If BN#_bn_naming#_CMPINT(*b, 0)=0
  BN#_bn_naming#_INT(*dest, 1)
 ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
  *seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
  *tmp1 = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
  *tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
  If *seed=0
   ProcedureReturn 0
  EndIf
  bits = BN#_bn_naming#_USED_BITS(*b)
  BN#_bn_naming#_MOV(*seed, *b)
  BN#_bn_naming#_INT(*dest, 1)
  BN#_bn_naming#_MOV(*tmp1, *a)
  For i = 1 To bits
   If *seed\n[0] & 1
    BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
    BN#_bn_naming#_MOV(*dest, *tmp2)
   EndIf
   If i<>bits
    BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
    BN#_bn_naming#_MOV(*tmp1, *tmp2)
    BN#_bn_naming#_SHR1(*seed)
   EndIf
  Next
  FreeMemory(*seed)
 EndIf
 ProcedureReturn *dest
EndProcedure

;- BN_POWINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_POWINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 Protected *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, seed.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or b<0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 BN#_bn_naming#_INT(*dest, 0)
 If b=0
  BN#_bn_naming#_INT(*dest, 1)
 ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
  *tmp1 = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*2)
  *tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
  If *tmp1=0
   ProcedureReturn 0
  EndIf
  bits = BN#_bn_naming#_USED_BITS(*b)
  seed = b
  BN#_bn_naming#_INT(*dest, 1)
  BN#_bn_naming#_MOV(*tmp1, *a)
  While seed>0
   If seed&1
    BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
    BN#_bn_naming#_MOV(*dest, *tmp2)
   EndIf
   seed>>1
   If seed
    BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
    BN#_bn_naming#_MOV(*tmp1, *tmp2)
   EndIf
  Wend
  FreeMemory(*tmp1)
 EndIf
 ProcedureReturn *dest
EndProcedure

;- BN_POW_MOD(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER, *m.BIG_NUMBER)
Procedure.l BN#_bn_naming#_POW_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *m.BIG_NUMBER#_bn_naming#)
 Protected *seed.BIG_NUMBER#_bn_naming#, *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, bits.l, i.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0 Or *m=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 BN#_bn_naming#_INT(*dest, 0)
 If BN#_bn_naming#_CMPINT(*b, 0)=0
  If BN#_bn_naming#_CMPINT(*m, 1)=1
   BN#_bn_naming#_INT(*dest, 1)
  EndIf
 ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
  *seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
  *tmp1 = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
  *tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
  If *seed=0
   ProcedureReturn 0
  EndIf
  bits = BN#_bn_naming#_USED_BITS(*b)
  BN#_bn_naming#_MOV(*seed, *b)
  BN#_bn_naming#_INT(*dest, 1)
  BN#_bn_naming#_MOV(*tmp1, *a)
  For i = 1 To bits
   If *seed\n[0] & 1
    BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
    BN#_bn_naming#_MOD(*dest, *tmp2, *m)
   EndIf
   If i<>bits
    BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
    BN#_bn_naming#_MOD(*tmp1, *tmp2, *m)
    BN#_bn_naming#_SHR1(*seed)
   EndIf
  Next
  FreeMemory(*seed)
 EndIf
 ProcedureReturn *dest
EndProcedure

;- BN_POW_MODINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER, m.l)
Procedure.l BN#_bn_naming#_POW_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, m.l)
 Protected *seed.BIG_NUMBER#_bn_naming#, *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, bits.l, i.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 BN#_bn_naming#_INT(*dest, 0)
 If BN#_bn_naming#_CMPINT(*b, 0)=0
  If m>1
   BN#_bn_naming#_INT(*dest, 1)
  EndIf
 ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
  *seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
  *tmp1 = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
  *tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
  If *seed=0
   ProcedureReturn 0
  EndIf
  bits = BN#_bn_naming#_USED_BITS(*b)
  BN#_bn_naming#_MOV(*seed, *b)
  BN#_bn_naming#_INT(*dest, 1)
  BN#_bn_naming#_MOV(*tmp1, *a)
  For i = 1 To bits
   If *seed\n[0] & 1
    BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
    BN#_bn_naming#_MODINT(*dest, *tmp2, m)
   EndIf
   If i<>bits
    BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
    BN#_bn_naming#_MODINT(*tmp1, *tmp2, m)
    BN#_bn_naming#_SHR1(*seed)
   EndIf
  Next
  FreeMemory(*seed)
 EndIf
 ProcedureReturn *dest
EndProcedure

;- BN_SQR(*dest.BIG_NUMBER, *a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SQR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
 Protected *last.BIG_NUMBER#_bn_naming#, *rem.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, Result.q, Last.q, n.q
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 If BN#_bn_naming#_USED_LONGS(*a) = 1
  !MOV dword [p.v_n+4], 0
  !MOV dword [p.v_Result+4], 0
  !MOV edx, dword [p.p_a]
  !MOV eax, dword [edx]
  !MOV dword [p.v_n], eax
  !SHR eax, 1
  !MOV dword [p.v_Result], eax
  If Result < 2
   If Result < 1
    BN#_bn_naming#_INT(*dest, 0)
   Else
    BN#_bn_naming#_INT(*dest, 1)
   EndIf
   ProcedureReturn *dest
  EndIf
  Repeat
   Last = Result
   Result = (Result + (n / Result)) / 2
  Until Last <= Result
  BN#_bn_naming#_INT(*dest, Last)
 Else
  *last = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#) * 3)
  *rem = *last + SizeOf(BIG_NUMBER#_bn_naming#)
  *tmp = *rem + SizeOf(BIG_NUMBER#_bn_naming#)
  If *last = 0
   ProcedureReturn 0
  EndIf
  BN#_bn_naming#_MOV(*dest, *a)
  BN#_bn_naming#_SHR1(*dest)
  Repeat
   BN#_bn_naming#_MOV(*last, *dest)
   BN#_bn_naming#_DIV(*tmp, *rem, *a, *dest)
   BN#_bn_naming#_ADD(*dest, *dest, *tmp)
   BN#_bn_naming#_SHR1(*dest)
  Until BN#_bn_naming#_CMP(*last, *dest) <= 0
  BN#_bn_naming#_MOV(*dest, *last)
  FreeMemory(*last)
 EndIf
 ProcedureReturn *dest
EndProcedure

;div as you know from school.. just with binary numbers
;- BN_DIV(*dest.BIG_NUMBER, *destRem.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
;- TODO: rewrite in assembler (IMPORTANT)
Procedure.l BN#_bn_naming#_DIV(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 Protected *seed.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, i.l, offset.l, bitsInB.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *destRem=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_destRem+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !XOR eax, eax
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV dword [esi+ecx*4], eax
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV dword [esi+(%-1)*4], eax
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !BNPV_POP esi,edi
 If BN#_bn_naming#_CMPINT(*a, 0)=0
  ProcedureReturn *dest
 ElseIf BN#_bn_naming#_CMPINT(*b, 0)=0
  ProcedureReturn 0
 EndIf
 Select BN#_bn_naming#_CMP(*a, *b)
  Case -1 ;a<b
   BN#_bn_naming#_MOV(*destRem, *a)
   ProcedureReturn *dest
  Case 0 ;a=b
   *dest\n[0] = 1
   ProcedureReturn *dest
  Case 1 ;a>b
   bitsInB = BN#_bn_naming#_USED_BITS(*b)
   If bitsInB<=32
    ProcedureReturn BN#_bn_naming#_DIVINT(*dest, *destRem, *a, *b\n[0])
   Else
    *seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*2)
    *tmp = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
    If *seed=0
     ProcedureReturn 0
    EndIf
    offset = BN#_bn_naming#_USED_BITS(*a) - bitsInB
    BN#_bn_naming#_SHL(*seed, *b, offset)
    BN#_bn_naming#_MOV(*destRem, *a)
    For i=0 To offset
     BN#_bn_naming#_SHL1(*dest)
     If BN#_bn_naming#_CMP(*seed, *destRem)<=0
      BN#_bn_naming#_SUB(*tmp, *destRem, *seed)
      BN#_bn_naming#_MOV(*destRem, *tmp)
      *dest\n[0] | 1
     EndIf
     BN#_bn_naming#_SHR1(*seed)
    Next
    FreeMemory(*seed)
   EndIf
 EndSelect
 ProcedureReturn *dest
EndProcedure

;- BN_DIVINT(*dest.BIG_NUMBER, *destRem.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_DIVINT(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *destRem=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_destRem+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !XOR eax, eax
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV dword [esi+ecx*4], eax
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV dword [esi+(%-1)*4], eax
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !BNPV_POP esi,edi
 If BN#_bn_naming#_CMPINT(*a, 0)=0
  ProcedureReturn *dest
 ElseIf b=0
  ProcedureReturn 0
 EndIf
 Select BN#_bn_naming#_CMPINT(*a, b)
  Case -1 ;a<b
   BN#_bn_naming#_MOV(*destRem, *a)
   ProcedureReturn *dest
  Case 0 ;a=b
   *dest\n[0] = 1
   ProcedureReturn *dest
  Case 1 ;a>b
   !BNPV_PUSH esi,edi,ebx
   !MOV esi, dword [p.p_a+BNPV_OFFSET]
   !MOV edi, dword [p.p_dest+BNPV_OFFSET]
   !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
   !@@:
    !CMP dword [esi+ecx*4], 0
    !JNE @f
    !DEC ecx
   !JNS @b
   !@@:
   !CMP ecx, 0
   !JL @@BN#_bn_naming#_DIVINT_endif1
    !XOR eax, eax
    !XOR edx, edx
    !MOV ebx, dword [p.v_b+BNPV_OFFSET]
    !@@:
     !MOV eax, dword [esi+ecx*4]
     !DIV ebx
     !MOV dword [edi+ecx*4], eax
     !MOV eax, edx
     !DEC ecx
    !JNS @b
    !MOV edi, dword [p.p_destRem+BNPV_OFFSET]
    !MOV dword [edi], edx
   !@@BN#_bn_naming#_DIVINT_endif1:
   !BNPV_POP esi,edi,ebx
 EndSelect
 ProcedureReturn *dest
EndProcedure

;- BN_MOD(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 Protected *tmp.BIG_NUMBER#_bn_naming#, result.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 *tmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#))
 If *tmp=0 : ProcedureReturn 0 : EndIf
 result = BN#_bn_naming#_DIV(*tmp, *dest, *a, *b)
 FreeMemory(*tmp)
 If result=0
  ProcedureReturn 0
 Else
  ProcedureReturn *dest
 EndIf
EndProcedure

;- BN_MODINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH edi
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !XOR eax, eax
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !BNPV_POP edi
 If BN#_bn_naming#_CMPINT(*a, 0)=0
  ProcedureReturn *dest
 ElseIf b=0
  ProcedureReturn 0
 EndIf
 Select BN#_bn_naming#_CMPINT(*a, b)
  Case -1 ;a<b
   BN#_bn_naming#_MOV(*dest, *a)
   ProcedureReturn *dest
  Case 0 ;a=b
   ProcedureReturn *dest
  Case 1 ;a>b
   !BNPV_PUSH esi,edi,ebx
   !MOV esi, dword [p.p_a+BNPV_OFFSET]
   !MOV edi, dword [p.p_dest+BNPV_OFFSET]
   !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
   !@@:
    !CMP dword [esi+ecx*4], 0
    !JNE @f
    !DEC ecx
   !JNS @b
   !@@:
   !CMP ecx, 0
   !JL @@BN#_bn_naming#_MODINT_endif1
    !XOR eax, eax
    !XOR edx, edx
    !MOV ebx, dword [p.v_b+BNPV_OFFSET]
    !@@:
     !MOV eax, dword [esi+ecx*4]
     !DIV ebx
     !MOV eax, edx
     !DEC ecx
    !JNS @b
    !MOV dword [edi], edx
   !@@BN#_bn_naming#_MODINT_endif1:
   !BNPV_POP esi,edi,ebx
 EndSelect
 ProcedureReturn *dest
EndProcedure

; Procedure.q GCD(a.q, b.q)
;  Protected shift.l, diff.q
;  If a=0 Or b=0
;   ProcedureReturn a | b
;  EndIf
;  shift = 0
;  While ((a | b) & 1) = 0
;   a >> 1
;   b >> 1
;   shift + 1
;  Wend
;  While (a & 1) = 0
;   a >> 1
;  Wend
;  Repeat
;   While (b & 1) = 0
;    b >> 1
;   Wend
;   If a <= b
;    b - a
;   Else
;    diff = a - b
;    a = b
;    b = diff
;   EndIf
;   b >> 1
;  Until b = 0
;  ProcedureReturn a << shift
; EndProcedure
;- BN_GCD(*dest.BIG_NUMBER, *b.BIG_NUMBER, *n.BIG_NUMBER)
Procedure.l BN#_bn_naming#_GCD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 Protected shift.l, *atmp.BIG_NUMBER#_bn_naming#, *btmp.BIG_NUMBER#_bn_naming#
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 If BN#_bn_naming#_CMPINT(*a, 0)=0
  BN#_bn_naming#_MOV(*dest, *b)
  ProcedureReturn *dest
 ElseIf BN#_bn_naming#_CMPINT(*b, 0)=0
  BN#_bn_naming#_MOV(*dest, *a)
  ProcedureReturn *dest
 EndIf
 *atmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*2)
 *btmp = *atmp+SizeOf(BIG_NUMBER#_bn_naming#)
 If *atmp=0
  ProcedureReturn 0
 EndIf
 shift = 0
 BN#_bn_naming#_MOV(*atmp, *a)
 BN#_bn_naming#_MOV(*btmp, *b)
 While ((*atmp\n[0] | *btmp\n[0]) & 1) = 0
  BN#_bn_naming#_SHR1(*atmp)
  BN#_bn_naming#_SHR1(*btmp)
  shift + 1
 Wend
 While (*atmp\n[0] & 1) = 0
  BN#_bn_naming#_SHR1(*atmp)
 Wend
 Repeat
  While (*btmp\n[0] & 1) = 0
   BN#_bn_naming#_SHR1(*btmp)
  Wend
  If BN#_bn_naming#_CMP(*atmp, *btmp)<=0
   BN#_bn_naming#_SUB(*dest, *btmp, *atmp)
   BN#_bn_naming#_MOV(*btmp, *dest)
  Else
   BN#_bn_naming#_SUB(*dest, *atmp, *btmp)
   BN#_bn_naming#_MOV(*atmp, *btmp)
   BN#_bn_naming#_MOV(*btmp, *dest)
  EndIf
 Until BN#_bn_naming#_CMPINT(*btmp, 0)=0
 BN#_bn_naming#_SHL(*dest, *atmp, shift)
 FreeMemory(*atmp)
 ProcedureReturn *dest
EndProcedure

; Procedure.q invMod(b.q, n.q)
;  Protected b0.q, n0.q, t0.q, t.q, q.q, r.q, temp.q
;  b0 = b
;  n0 = n
;  t0 = 0
;  t = 1
;  q = Round(n0 / b0,0)
;  r = n0 % b0
;  While r > 0
;   If t0 >= q * t
;    temp = (t0 - (q * t)) % n
;   Else
;    temp = n - (((q * t) - t0) % n)
;   EndIf
;   t0 = t
;   t = temp
;   n0 = b0
;   b0 = r
;   q = Round(n0 / b0,0)
;   r = n0 % b0
;  Wend
;  If b0 <> 1
;   ProcedureReturn -1 ;b has no inverse to modulo n
;  Else
;   ProcedureReturn t % n
;  EndIf
; EndProcedure
;- BN_INV_MOD(*dest.BIG_NUMBER, *b.BIG_NUMBER, *n.BIG_NUMBER)
Procedure.l BN#_bn_naming#_INV_MOD(*dest.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *n.BIG_NUMBER#_bn_naming#)
 Protected *b0.BIG_NUMBER#_bn_naming#, *n0.BIG_NUMBER#_bn_naming#, *t0.BIG_NUMBER#_bn_naming#, *t.BIG_NUMBER#_bn_naming#, *q.BIG_NUMBER#_bn_naming#, *r.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, Result.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *b=0 Or *n=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 *b0 = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*7)
 *n0 = *b0+SizeOf(BIG_NUMBER#_bn_naming#)
 *t0 = *n0+SizeOf(BIG_NUMBER#_bn_naming#)
 *t = *t0+SizeOf(BIG_NUMBER#_bn_naming#)
 *q = *t+SizeOf(BIG_NUMBER#_bn_naming#)
 *r = *q+SizeOf(BIG_NUMBER#_bn_naming#)
 *tmp = *r+SizeOf(BIG_NUMBER#_bn_naming#)
 If *b0=0
  ProcedureReturn 0
 EndIf
 BN#_bn_naming#_MOV(*b0, *b)
 BN#_bn_naming#_MOV(*n0, *n)
 BN#_bn_naming#_INT(*t0, 0)
 BN#_bn_naming#_INT(*t, 1)
 BN#_bn_naming#_DIV(*q, *r, *n0, *b0)
 While BN#_bn_naming#_CMPINT(*r,0)=1
  BN#_bn_naming#_MUL(*tmp, *q, *t)
  If BN#_bn_naming#_CMP(*t0, *tmp)>=0
   BN#_bn_naming#_SUB(*dest, *t0, *tmp)
   BN#_bn_naming#_MOD(*tmp, *dest, *n)
  Else
   BN#_bn_naming#_SUB(*dest, *tmp, *t0)
   BN#_bn_naming#_MOD(*tmp, *dest, *n)
   BN#_bn_naming#_SUB(*dest, *n, *tmp)
   BN#_bn_naming#_MOV(*tmp, *dest)
  EndIf
  BN#_bn_naming#_MOV(*t0, *t)
  BN#_bn_naming#_MOV(*t, *tmp)
  BN#_bn_naming#_MOV(*n0, *b0)
  BN#_bn_naming#_MOV(*b0, *r)
  BN#_bn_naming#_DIV(*q, *r, *n0, *b0)
 Wend
 If BN#_bn_naming#_CMPINT(*b0, 1)=1
  Result = 0
 Else
  Result = *dest
  BN#_bn_naming#_MOD(*dest, *t, *n)
 EndIf
 FreeMemory(*b0)
 ProcedureReturn Result
EndProcedure

;- BN_RND(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_RND(*dest.BIG_NUMBER#_bn_naming#)
 !if 0 ;make pb include the lib for Random()
  Random(1)
 !end if
 CompilerIf _bn_checkmem=#True
 If *dest=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 CompilerIf _bn_size_optimized
 Protected i.l
 !MOV dword [p.v_i], BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
;   !MOV eax, $FFFF
;   !CALL PB_Random
  !PUSH $FFFF
  !CALL _PB_Random@4
  !MOV edx, dword [p.p_dest]
  !MOV ecx, dword [p.v_i]
  !MOV word [edx+ecx*4], ax
;   !MOV eax, $FFFF
;   !CALL PB_Random
  !PUSH $FFFF
  !CALL _PB_Random@4
  !MOV edx, dword [p.p_dest]
  !MOV ecx, dword [p.v_i]
  !MOV word [edx+ecx*4+2], ax
  !DEC dword [p.v_i]
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS*2
;   !MOV eax, $FFFF
;   !CALL PB_Random
  !PUSH $FFFF
  !CALL _PB_Random@4
  !MOV edx, dword [p.p_dest]
  !MOV word [edx+(%-1)*2], ax
 !end repeat
 CompilerEndIf
 ProcedureReturn *dest
EndProcedure

;- BN_RND_MAX(*dest.BIG_NUMBER, bits.l)
Procedure.l BN#_bn_naming#_RND_MAX(*dest.BIG_NUMBER#_bn_naming#, bits.l)
 !if 0 ;make pb include the lib for Random()
  Random(1)
 !end if
 CompilerIf _bn_checkmem=#True
 If *dest=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !MOV ecx, dword [p.v_bits]
 !SHR ecx, 5
 !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !JA @@BN#_bn_naming#_RND_MAX_next1
 !XOR eax, eax
 !MOV edx, dword [p.p_dest]
 !@@:
  !MOV dword [edx+ecx*4], eax
  !INC ecx
  !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !JBE @b
 !@@BN#_bn_naming#_RND_MAX_next1:
 !MOV ecx, dword [p.v_bits]
 !SHR ecx, 4
 !JZ @@BN#_bn_naming#_RND_MAX_endif1
 !DEC ecx
 !@@:
  !PUSH ecx
;   !MOV eax, $FFFF
;   !CALL PB_Random
  !PUSH $FFFF
  !CALL _PB_Random@4
  !POP ecx
  !MOV edx, dword [p.p_dest]
  !MOV word [edx+ecx*2], ax
  !DEC ecx
 !JNS @b
 !@@BN#_bn_naming#_RND_MAX_endif1:
;  !MOV eax, $FFFF
;  !CALL PB_Random
 !PUSH $FFFF
 !CALL _PB_Random@4
 !MOV edx, eax
 !MOV eax, dword [p.v_bits]
 !MOV ecx, eax
 !SHR eax, 4
 !AND ecx, $0000000F
 !JZ @@BN#_bn_naming#_RND_MAX_endif2
 !NEG ecx
 !ADD ecx, $00000010
 !SHR edx, cl
 !MOV ecx, dword [p.p_dest]
 !MOV word [ecx+eax*2], dx
 !@@BN#_bn_naming#_RND_MAX_endif2:
 ProcedureReturn *dest
EndProcedure

;- BN_MOV(*dest.BIG_NUMBER, *a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_MOV(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV eax, dword [esi+ecx*4]
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV eax, dword [esi+(%-1)*4]
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !BNPV_POP esi,edi
 ProcedureReturn *dest
EndProcedure

;- BN_NOT(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_NOT(*dest.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH edi
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !NOT dword [edi+ecx*4]
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !NOT dword [edi+(%-1)*4]
 !end repeat
 CompilerEndIf
 !BNPV_POP edi
 ProcedureReturn *dest
EndProcedure

;- BN_AND(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_AND(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edx, dword [p.p_b+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV eax, dword [esi+ecx*4]
  !AND eax, dword [edx+ecx*4]
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV eax, dword [esi+(%-1)*4]
  !AND eax, dword [edx+(%-1)*4]
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !BNPV_POP esi,edi
 ProcedureReturn *dest
EndProcedure

;- BN_OR(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_OR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edx, dword [p.p_b+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV eax, dword [esi+ecx*4]
  !OR eax, dword [edx+ecx*4]
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV eax, dword [esi+(%-1)*4]
  !OR eax, dword [edx+(%-1)*4]
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !BNPV_POP esi,edi
 ProcedureReturn *dest
EndProcedure

;- BN_XOR(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_XOR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0 Or *b=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edx, dword [p.p_b+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV eax, dword [esi+ecx*4]
  !XOR eax, dword [edx+ecx*4]
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV eax, dword [esi+(%-1)*4]
  !XOR eax, dword [edx+(%-1)*4]
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !BNPV_POP esi,edi
 ProcedureReturn *dest
EndProcedure

;- BN_SHL(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_SHL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH ebx,esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !CMP dword [p.v_b+BNPV_OFFSET], 32
 !JB @@BN#_bn_naming#_SHL_endif1
 !XOR eax, eax
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV dword [edi+ecx*4], eax
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 CompilerEndIf
 !@@BN#_bn_naming#_SHL_endif1:
 !XOR edx, edx
 !MOV eax, dword [p.v_b+BNPV_OFFSET]
 !SHR eax, 5
 !MOV ebx, BIG_NUMBER#_bn_naming#_LONGS-1
 !MOV ecx, ebx
 !SUB ecx, eax
 !JS @@BN#_bn_naming#_SHL_next1
 !@@BN#_bn_naming#_SHL_for1:
  !MOV eax, dword [esi+ecx*4]
  !MOV dword [edi+ebx*4], eax
  !DEC ebx
  !DEC ecx
  !JNS @@BN#_bn_naming#_SHL_for1
 !@@BN#_bn_naming#_SHL_next1:
 ;progress edx (= b mod 32)
 !MOV edx, dword [p.v_b+BNPV_OFFSET]
 !AND edx, $0000001F
 !MOV ecx, edx
 !CMP ecx, 0
 !JE @@BN#_bn_naming#_SHL_endproc
 !BN#_bn_naming#_SHL_a = BIG_NUMBER#_bn_naming#_LONGS-1
 !MOV edx, dword [edi+BN#_bn_naming#_SHL_a*4]
 !while BN#_bn_naming#_SHL_a > 0
  !MOV eax, dword [edi+BN#_bn_naming#_SHL_a*4-4]
  !SHLD edx, eax, cl
  !MOV dword [edi+BN#_bn_naming#_SHL_a*4], edx
  !MOV edx, eax
  !BN#_bn_naming#_SHL_a = BN#_bn_naming#_SHL_a - 1
 !end while
 !MOV eax, dword [edi]
 !SHL eax, cl
 !MOV dword [edi], eax
 !@@BN#_bn_naming#_SHL_endproc:
 !BNPV_POP ebx,esi,edi
 ProcedureReturn *dest
EndProcedure

;- BN_SHL1(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SHL1(*dest.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !MOV eax, dword [p.p_dest]
 !SHL dword [eax], 1
 !if BIG_NUMBER#_bn_naming#_LONGS>1
  CompilerIf _bn_size_optimized
  !MOV ecx, 1
  !@@:
   !RCL dword [eax+ecx*4], 1
   !INC ecx
   !CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
  !JBE @b
  CompilerElse
  !repeat BIG_NUMBER#_bn_naming#_LONGS-1
   !RCL dword [eax+%*4], 1
  !end repeat
  CompilerEndIf
 !end if
 ProcedureReturn *dest
EndProcedure

;- BN_SHR(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_SHR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !BNPV_PUSH ebx,esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edi, dword [p.p_dest+BNPV_OFFSET]
 !CMP dword [p.v_b+BNPV_OFFSET], 32
 !JB @@BN#_bn_naming#_SHR_endif1
 !XOR eax, eax
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV dword [edi+(%-1)*4], eax
 !end repeat
 !@@BN#_bn_naming#_SHR_endif1:
 !XOR edx, edx
 !MOV eax, dword [p.v_b+BNPV_OFFSET]
 !SHR eax, 5
 !XOR ecx, ecx
 !MOV ebx, eax
 !CMP ebx, BIG_NUMBER#_bn_naming#_LONGS-1
 !JA @@BN#_bn_naming#_SHR_next1
 !@@BN#_bn_naming#_SHR_for1:
  !MOV eax, dword [esi+ebx*4]
  !MOV dword [edi+ecx*4], eax
  !INC ecx
  !INC ebx
  !CMP ebx, BIG_NUMBER#_bn_naming#_LONGS-1
  !JBE @@BN#_bn_naming#_SHR_for1
 !@@BN#_bn_naming#_SHR_next1:
 ;progress edx (= b mod 32)
 !MOV edx, dword [p.v_b+BNPV_OFFSET]
 !AND edx, $0000001F
 !MOV ecx, edx
 !CMP ecx, 0
 !JE @@BN#_bn_naming#_SHR_endproc
 !BN#_bn_naming#_SHR_a = 0
 !MOV eax, dword [edi]
 !while BN#_bn_naming#_SHR_a < BIG_NUMBER#_bn_naming#_LONGS-1
  !MOV edx, dword [edi+BN#_bn_naming#_SHR_a*4+4]
  !SHRD eax, edx, cl
  !MOV dword [edi+BN#_bn_naming#_SHR_a*4], eax
  !MOV eax, edx
  !BN#_bn_naming#_SHR_a = BN#_bn_naming#_SHR_a + 1
 !end while
 !MOV eax, dword [edi+(BIG_NUMBER#_bn_naming#_LONGS-1)*4]
 !SHR eax, cl
 !MOV dword [edi+(BIG_NUMBER#_bn_naming#_LONGS-1)*4], eax
 !@@BN#_bn_naming#_SHR_endproc:
 !BNPV_POP ebx,esi,edi
 ProcedureReturn *dest
EndProcedure

;- BN_SHR1(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SHR1(*dest.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *dest=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !MOV eax, dword [p.p_dest]
 !SHR dword [eax+BIG_NUMBER#_bn_naming#_LONGS*4-4], 1
 !if BIG_NUMBER#_bn_naming#_LONGS>1
  CompilerIf _bn_size_optimized
  !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-2
  !@@:
   !RCR dword [eax+ecx*4], 1
   !DEC ecx
  !JNS @b
  CompilerElse
  !repeat BIG_NUMBER#_bn_naming#_LONGS-1
   !RCR dword [eax+BIG_NUMBER#_bn_naming#_LONGS*4-%*4-4], 1
  !end repeat
  CompilerEndIf
 !end if
 ProcedureReturn *dest
EndProcedure

;- BN_CMP(*a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_CMP(*a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *a=0 Or *b=0
  ProcedureReturn -2
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi,edi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !MOV edi, dword [p.p_b+BNPV_OFFSET]
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !MOV eax, dword [esi+ecx*4]
  !CMP eax, dword [edi+ecx*4]
  !JB @@BN#_bn_naming#_CMP_aLTb
  !JA @@BN#_bn_naming#_CMP_aGTb
  !DEC ecx
 !JNS @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS
  !MOV eax, dword [esi+(BIG_NUMBER#_bn_naming#_LONGS-%)*4]
  !CMP eax, dword [edi+(BIG_NUMBER#_bn_naming#_LONGS-%)*4]
  !JB @@BN#_bn_naming#_CMP_aLTb
  !JA @@BN#_bn_naming#_CMP_aGTb
 !end repeat
 CompilerEndIf
 !@@BN#_bn_naming#_CMP_aEQb:
 !BNPV_POP esi,edi
 ProcedureReturn 0
 !@@BN#_bn_naming#_CMP_aLTb:
 !BNPV_POP esi,edi
 ProcedureReturn -1
 !@@BN#_bn_naming#_CMP_aGTb:
 !BNPV_POP esi,edi
 ProcedureReturn 1
EndProcedure

;- BN_CMPINT(*a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_CMPINT(*a.BIG_NUMBER#_bn_naming#, b.l)
 CompilerIf _bn_checkmem=#True
 If *a=0
  ProcedureReturn -2
 EndIf
 CompilerEndIf
 !BNPV_PUSH esi
 !MOV esi, dword [p.p_a+BNPV_OFFSET]
 !XOR eax, eax
 CompilerIf _bn_size_optimized
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !MOV edx, 1
 !@@:
  !CMP dword [esi+edx*4], eax
  !JNE @@BN#_bn_naming#_CMPINT_aGTb
  !INC edx
  !DEC ecx
 !JNZ @b
 CompilerElse
 !repeat BIG_NUMBER#_bn_naming#_LONGS-1
  !CMP dword [esi+%*4], eax
  !JNE @@BN#_bn_naming#_CMPINT_aGTb
 !end repeat
 CompilerEndIf
 !MOV eax, dword [p.v_b+BNPV_OFFSET]
 !CMP dword [esi], eax
 !JB @@BN#_bn_naming#_CMPINT_aLTb
 !JA @@BN#_bn_naming#_CMPINT_aGTb
 !@@BN#_bn_naming#_CMPINT_aEQb:
 !BNPV_POP esi
 ProcedureReturn 0
 !@@BN#_bn_naming#_CMPINT_aLTb:
 !BNPV_POP esi
 ProcedureReturn -1
 !@@BN#_bn_naming#_CMPINT_aGTb:
 !BNPV_POP esi
 ProcedureReturn 1
EndProcedure

;- BN_IS_EVEN(*a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_IS_EVEN(*a.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *a=0
  ProcedureReturn -1
 EndIf
 CompilerEndIf
 !MOV eax, dword [p.p_a]
 !BT word [eax], 0
 !JNC @@BN#_bn_naming#_ISEVEN_Even
 !@@BN#_bn_naming#_ISEVEN_Odd:
 ProcedureReturn 0
 !@@BN#_bn_naming#_ISEVEN_Even:
 ProcedureReturn 1
EndProcedure

; Procedure.l Witness(A.q, i.q, N.q)
;  Protected X.q, Y.q, j.q, k.l
;  If i = 0
;   ProcedureReturn 1
;  EndIf
; 
;  k = 0
;  Repeat
;   k + 1
;   j = ($FFFFFFFFFFFFFFFF & i >> k)
;  Until j = 0
;  k - 1
; 
;  X = 1
;  j = ($FFFFFFFFFFFFFFFF & i) >> k
;  While k+1 <> 0 And X <> 0
;   Y = ( X * X ) % N
;   If Y = 1 And X <> 1 And X <> N - 1
;    ProcedureReturn 0
;   EndIf
; 
;   If j % 2 <> 0
;    Y = ( A * Y ) % N
;   EndIf
; 
;   k - 1
;   j = ($FFFFFFFFFFFFFFFF & i) >> k
; 
;   X = Y
;  Wend
;  ProcedureReturn X
; EndProcedure
; 
; Procedure.l CheckPrime(N.q)
;  If Witness(RandInt(2, N-2), N-1, N) = 1
;   ProcedureReturn 1
;  Else
;   ProcedureReturn 0
;  EndIf
; EndProcedure
;- BN_IS_PRIME(*N.BIG_NUMBER)
Procedure.l BN#_bn_naming#_IS_PRIME(*N.BIG_NUMBER#_bn_naming#)
 Protected *A.BIG_NUMBER#_bn_naming#, *i.BIG_NUMBER#_bn_naming#, *X.BIG_NUMBER#_bn_naming#, *Y.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, k.l, w.l
 CompilerIf _bn_checkmem=#True
 If *N=0
  ProcedureReturn -1
 EndIf
 CompilerEndIf
 If BN#_bn_naming#_CMPINT(*N,100)>0
  *A = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*5)
  *i = *A+SizeOf(BIG_NUMBER#_bn_naming#)
  *X = *i+SizeOf(BIG_NUMBER#_bn_naming#)
  *Y = *X+SizeOf(BIG_NUMBER#_bn_naming#)
  *tmp = *Y+SizeOf(BIG_NUMBER#_bn_naming#)
  If *A=0
   ProcedureReturn -1
  EndIf
  BN#_bn_naming#_SUBINT(*i, *N, 1)
  k = BN#_bn_naming#_USED_BITS(*i) - 1
  BN#_bn_naming#_SUBINT(*tmp, *i, 1)
  BN#_bn_naming#_RND_MAX(*A, (#BIG_NUMBER#_bn_naming#_LONGS*32)-(k+3))
;;  While BN#_bn_naming#_CMP(*A, *tmp)=1
;;   BN#_bn_naming#_SHR(*X, *A, 1)
;;   BN#_bn_naming#_MOV(*A, *X)
;;  Wend
  BN#_bn_naming#_INT(*X, 1)
  w = #True
  While k+1 <> 0 And BN#_bn_naming#_CMPINT(*X, 0) <> 0
   BN#_bn_naming#_MUL(*tmp, *X, *X)
   BN#_bn_naming#_MOD(*Y, *tmp, *N)
   If BN#_bn_naming#_CMPINT(*Y, 1)=0 And BN#_bn_naming#_CMPINT(*X, 1)<>0 And BN#_bn_naming#_CMP(*X, *i)<>0
    w = #False
    Break
   EndIf
   BN#_bn_naming#_SHR(*tmp, *i, k)
   If *tmp\n[0] & 1
    BN#_bn_naming#_MUL(*tmp, *A, *Y)
    BN#_bn_naming#_MOD(*Y, *tmp, *N)
   EndIf
   k - 1
   BN#_bn_naming#_MOV(*X, *Y)
  Wend
  If BN#_bn_naming#_CMPINT(*X, 1)<>0
   w = #False
  EndIf
  FreeMemory(*A)
  ProcedureReturn w
 Else ;fast check for small primes
  Select *N\n[0]
   Case 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
    ProcedureReturn #True
   Default
    ProcedureReturn #False
  EndSelect
 EndIf
EndProcedure

;- BN_NEXT_PRIME(*dest.BIG_NUMBER, *a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_NEXT_PRIME(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
 Protected *tmp.BIG_NUMBER#_bn_naming#, scrTmp.l
 CompilerIf _bn_checkmem=#True
 If *dest=0 Or *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 *tmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#))
 If *tmp=0 : ProcedureReturn -1 : EndIf
 BN#_bn_naming#_MOV(*dest, *a)
 *dest\n[0] | 1
 scrTmp = #False
 Repeat
  BN#_bn_naming#_ADDINT(*tmp, *dest, 2)
  Swap *tmp, *dest
  scrTmp ! #True
 Until BN#_bn_naming#_IS_PRIME(*dest)
 If scrTmp
  Swap *tmp, *dest
  BN#_bn_naming#_MOV(*dest, *tmp)
 EndIf
;  scrTmp=BN#_bn_naming#_USED_BITS(*a)
;  Repeat
;   BN#_bn_naming#_RND_MAX(*dest, scrTmp)
;   *dest\n[0] | 1
;  Until BN#_bn_naming#_IS_PRIME(*dest)
 FreeMemory(*tmp)
 ProcedureReturn *dest
EndProcedure

;- BN_USED_BITS(*a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_USED_BITS(*a.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !MOV eax, BIG_NUMBER#_bn_naming#_LONGS*32
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !MOV edx, dword [p.p_a]
 !@@:
  !CMP dword [edx+ecx*4], 0
  !JNE @f
  !SUB eax, 32
  !DEC ecx
 !JNS @b
 !@@:
 !CMP eax, 0
 !JE @@BN#_bn_naming#_USED_BITS_endproc
 !SUB eax, 31
 !PUSH eax
 !BSR eax, dword [edx+ecx*4]
 !POP edx
 !ADD eax, edx
 !@@BN#_bn_naming#_USED_BITS_endproc:
 ProcedureReturn
EndProcedure

;- BN_USED_LONGS(*a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_USED_LONGS(*a.BIG_NUMBER#_bn_naming#)
 CompilerIf _bn_checkmem=#True
 If *a=0
  ProcedureReturn 0
 EndIf
 CompilerEndIf
 !MOV edx, dword [p.p_a]
 !MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
 !@@:
  !CMP dword [edx+ecx*4], 0
  !JNE @@BN#_bn_naming#_USED_LONGS_endproc
  !DEC ecx
 !JNS @b
 !@@BN#_bn_naming#_USED_LONGS_endproc:
 !MOV eax, ecx
 !INC eax
 ProcedureReturn
EndProcedure
EndMacro
User avatar
pcfreak
User
User
Posts: 75
Joined: Sat May 22, 2004 1:38 am

Post by pcfreak »

Here are some sample codes to use the functions above.

BigNumbers_RSATest.pb

Code: Select all

#size = 265

XIncludeFile "BigNumbers.pbi"
InitBigNumbers(544,_544)
InitBigNumbers(1088)

tmp1.BIG_NUMBER_544
tmp2.BIG_NUMBER_544

res.BIG_NUMBER
p.BIG_NUMBER
q.BIG_NUMBER
N.BIG_NUMBER
pN.BIG_NUMBER
e.BIG_NUMBER
d.BIG_NUMBER

message.BIG_NUMBER
encoded.BIG_NUMBER
decoded.BIG_NUMBER

OpenConsole()

t.l = timeGetTime_()
PrintN("Calculating p...")
BN_544_RND_MAX(tmp1, #size)
BN_544_NEXT_PRIME(tmp2, tmp1)
CopyMemory(tmp2, p, SizeOf(BIG_NUMBER_544))
;BN_VAL(p, "6910724503154360464421711409250620750683465471627739398629804509897031469720801")
PrintN(BN_STR(p))

PrintN("Calculating q...")
Repeat
 BN_544_RND_MAX(tmp1, #size)
 BN_544_NEXT_PRIME(tmp2, tmp1)
 CopyMemory(tmp2, q, SizeOf(BIG_NUMBER_544))
 ;BN_VAL(q, "52995404696611409340969190689663453034586021875872622931976653370908679948886921")
Until BN_CMP(p, q)<>0
PrintN(BN_STR(q))

PrintN("Calculating N...")
BN_MUL(N, p, q)
PrintN(BN_STR(N))

PrintN("Calculating Phi(N)...")
BN_SUB(pN, N, p)
BN_SUB(res, pN, q)
BN_ADDINT(pN, res, 1)
PrintN(BN_STR(pN))

PrintN("Calculating e...")
Repeat
 BN_544_RND_MAX(tmp1, #size)
 BN_544_NEXT_PRIME(tmp2, tmp1)
 CopyMemory(tmp2, e, SizeOf(BIG_NUMBER_544))
 ;BN_VAL(e, "3664050869228563609606231295899420165587379587690837513662722124761901918932789")
 BN_MOD(res, e, pN)
Until BN_CMP(e, p)<>0 And BN_CMP(e, q)<>0 And BN_CMPINT(res, 0)<>0
PrintN(BN_STR(e))

PrintN("Calculating d...")
BN_INV_MOD(d, e, pN)
PrintN(BN_STR(d))

BN_VAL(message, "2000000000000000000000000000000000000040200000000000000000000000000000000000003")
PrintN("message:")
PrintN(BN_STR(message))
BN_POW_MOD(encoded, message, e, N)
PrintN("encoded:")
PrintN(BN_STR(encoded))
BN_POW_MOD(decoded, encoded, d, N)
PrintN("decoded:")
PrintN(BN_STR(decoded))

PrintN("")
t = timeGetTime_() - t
PrintN("Finished in "+Str(t/60000)+"min "+Str((t/1000)%60)+"sec.")

PrintN("")
Print("Press -ENTER- to exit...") : Input()
BigNumbers_test.pb

Code: Select all

;Supported function
;==================
;
; BN_INT
; BN_VAL
; BN_STR
; BN_HEX
; BN_ADD
; BN_ADDINT
; BN_SUB
; BN_SUBINT
; BN_MUL
; BN_MULINT
; BN_POW
; BN_POWINT
; BN_POW_MOD
; BN_POW_MODINT
; BN_SQR
; BN_DIV (needs to be optimized)
; BN_DIVINT
; BN_MOD
; BN_MODINT
; BN_GCD
; BN_INV_MOD
; BN_RND
; BN_RND_MAX
; BN_MOV
; BN_NOT
; BN_AND
; BN_OR
; BN_XOR
; BN_SHL
; BN_SHL1
; BN_SHR
; BN_SHR1
; BN_CMP
; BN_CMPINT
; BN_IS_EVEN
; BN_IS_PRIME (needs to be optimized)
; BN_NEXT_PRIME (needs to be optimized)
; BN_USED_BITS
; BN_USED_LONGS
;
; - all unsingned integer operations

XIncludeFile "BigNumbers.pbi"

InitBigNumbers(64)

res.BIG_NUMBER
a.BIG_NUMBER
b.BIG_NUMBER
c.BIG_NUMBER

;============================================
;- BN_INT()
;============================================
Debug "Testing BN_INT()"

BN_INT(a, $2FBAE8A1)

Debug Hex($2FBAE8A1)
Debug "a = "+BN_HEX(a)
Debug ""

;============================================
;- BN_VAL()
;============================================
Debug "Testing BN_VAL()"

BN_VAL(a, StrU($2FBAE8A10,4))

Debug RSet(HexQ($2FBAE8A10),16,"0")
Debug "a = "+BN_HEX(a)
Debug ""

;============================================
;- BN_STR()
;============================================
Debug "Testing BN_STR()"

a\n[0]=$20F48003
a\n[1]=$0000B5E6

Debug StrU($0000B5E620F48003,4)
Debug "0x0000B5E620F48003"
Debug "a = "+BN_STR(a)
Debug ""

;============================================
;- BN_ADD()
;============================================
Debug "Testing BN_ADD()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000
b\n[0]=$FFFFFFFF
b\n[1]=$00000000

BN_ADD(res, a, b)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $FFFFFFFF+$FFFFFFFF
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""

;============================================
;- BN_ADDINT()
;============================================
Debug "Testing BN_ADDINT()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000

BN_ADDINT(res, a, 1)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $FFFFFFFF+1
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""

;============================================
;- BN_SUB()
;============================================
Debug "Testing BN_SUB()"

a\n[0]=$FFFFFFFE
a\n[1]=$00000001
b\n[0]=$FFFFFFFF
b\n[1]=$00000000

BN_SUB(res, a, b)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $FFFFFFFF
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_SUBINT()
;============================================
Debug "Testing BN_SUBINT()"

a\n[0]=$00000001
a\n[1]=$00000001

BN_SUBINT(res, a, 2)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $FFFFFFFF
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_MUL()
;============================================
Debug "Testing BN_MUL()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000
b\n[0]=$00000002
b\n[1]=$00000000

BN_MUL(res, a, b)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $00000001FFFFFFFE
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_MULINT()
;============================================
Debug "Testing BN_MULINT()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000

BN_MULINT(res, a, 2)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $00000001FFFFFFFE
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_POW()
;============================================
Debug "Testing BN_POW()"

a\n[0]=$00000007
a\n[1]=$00000000
b\n[0]=$0000000D
b\n[1]=$00000000

BN_POW(res, a, b)

Debug 96889010407
Debug PeekQ(res)
Debug ""

;============================================
;-  BN_POWINT()
;============================================
Debug "Testing BN_POWINT()"

a\n[0]=$00000007
a\n[1]=$00000000

BN_POWINT(res, a, 13)

Debug 96889010407
Debug PeekQ(res)
Debug ""

;============================================
;-  BN_POW_MOD()
;============================================
Debug "Testing BN_POW_MOD()"

a\n[0]=$00000007
a\n[1]=$00000000
b\n[0]=$0000000D
b\n[1]=$00000000
c\n[0]=$000000DD
c\n[1]=$00000000

BN_POW_MOD(res, a, b, c)

Debug 176
Debug PeekQ(res)
Debug ""

;============================================
;-  BN_POW_MODINT()
;============================================
Debug "Testing BN_POW_MODINT()"

a\n[0]=$00000007
a\n[1]=$00000000
b\n[0]=$0000000D
b\n[1]=$00000000

BN_POW_MODINT(res, a, b, $DD)

Debug 176
Debug PeekQ(res)
Debug ""

;============================================
;-  BN_SQR()
;============================================
Debug "Testing BN_SQR()"

a\n[0]=$FFFFFFFF
a\n[1]=$10101010

BN_SQR(res, a)

Debug StrU(PeekQ(a),4)
Debug StrU(PeekQ(res),4)
Debug $40201815
Debug BN_HEX(a)
Debug BN_HEX(res)
Debug "0000000040201815"
Debug ""

;============================================
;-  BN_DIV()
;============================================
Debug "Testing BN_DIV()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000
b\n[0]=$00000010
b\n[1]=$00000200

BN_DIV(res, c, b, a)

Debug $0000000000000200
Debug $0000000000000210
Debug StrU(PeekQ(res),4)
Debug StrU(PeekQ(c),4)
Debug BN_HEX(res)
Debug BN_HEX(c)
Debug ""

;============================================
;-  BN_DIVINT()
;============================================
Debug "Testing BN_DIVINT()"

b\n[0]=$00000000
b\n[1]=$00000010

BN_DIVINT(res, c, b, $F)

Debug $0000000111111111
Debug $0000000000000001
Debug StrU(PeekQ(res),4)
Debug StrU(PeekQ(c),4)
Debug BN_HEX(res)
Debug BN_HEX(c)
Debug ""

;============================================
;-  BN_MOD()
;============================================
Debug "Testing BN_MOD()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000
b\n[0]=$00000010
b\n[1]=$00000200

BN_MOD(res, b, a)

Debug $0000000000000210
Debug StrU(PeekQ(res),4)
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_MODINT()
;============================================
Debug "Testing BN_MODINT()"

b\n[0]=$00000010
b\n[1]=$00000200

BN_MODINT(res, b, 10)

Debug $0000000000000008
Debug StrU(PeekQ(res),4)
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_GCD()
;============================================
Debug "Testing BN_GCD()"

a\n[0]=$3DA6218C
a\n[1]=$00000000
b\n[0]=$35936359
b\n[1]=$0003AD97

BN_GCD(res, a, b)

Debug $0000000000007DA5
Debug StrU(PeekQ(res),4)
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_INV_MOD()
;============================================
Debug "Testing BN_INV_MOD()"

a\n[0]=$00000017
a\n[1]=$00000000
b\n[0]=$00000078
b\n[1]=$00000000

BN_INV_MOD(res, a, b)

Debug $000000000000002F
Debug StrU(PeekQ(res),4)
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_RND()
;============================================
Debug "Testing BN_RND()"

BN_RND(a)

Debug "a = "+BN_HEX(a)
Debug ""

;============================================
;-  BN_RND_MAX()
;============================================
Debug "Testing BN_RND_MAX()"

BN_RND_MAX(a, 48)

Debug "a = "+BN_HEX(a)
Debug ""

;============================================
;-  BN_MOV()
;============================================
Debug "Testing BN_MOV()"

a\n[0]=$7F7F7F7F
a\n[1]=$7F7F7F7F
b\n[0]=$00000000
b\n[1]=$00000000

BN_MOV(b, a)
Debug "a = "+BN_HEX(a)
Debug "b = "+BN_HEX(b)
Debug ""

;============================================
;-  BN_NOT()
;============================================
Debug "Testing BN_NOT()"

a\n[0]=$7F7F7F7F
a\n[1]=$7F7F7F7F

Debug "a = "+BN_HEX(a)
BN_NOT(a)
Debug "NOT = "+BN_HEX(a)
Debug ""

;============================================
;-  BN_AND()
;============================================
Debug "Testing BN_AND()"

a\n[0]=$FFFF0000
a\n[1]=$0000FFFF
b\n[0]=$EEEEEEEE
b\n[1]=$EEEEEEEE

BN_AND(res, a, b)

Debug "a = "+BN_HEX(a)
Debug "b = "+BN_HEX(b)
Debug "AND = "+BN_HEX(res)
Debug ""

;============================================
;-  BN_OR()
;============================================
Debug "Testing BN_OR()"

a\n[0]=$FFFF0000
a\n[1]=$00000000
b\n[0]=$00000000
b\n[1]=$0000FFFF

BN_OR(res, a, b)

Debug "a = "+BN_HEX(a)
Debug "b = "+BN_HEX(b)
Debug "OR = "+BN_HEX(res)
Debug ""

;============================================
;-  BN_XOR()
;============================================
Debug "Testing BN_XOR()"

a\n[0]=$FFFFFF00
a\n[1]=$FF000000
b\n[0]=$FF000000
b\n[1]=$FF00FFFF

BN_XOR(res, a, b)

Debug "a = "+BN_HEX(a)
Debug "b = "+BN_HEX(b)
Debug "XOR = "+BN_HEX(res)
Debug ""

;============================================
;-  BN_SHL()
;============================================
Debug "Testing BN_SHL()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000

BN_SHL(res, a, 1)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $00000001FFFFFFFE
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""

;============================================
;-  BN_SHL1()
;============================================
Debug "Testing BN_SHL1()"

a\n[0]=$FFFFFFFF
a\n[1]=$00000000

BN_SHL1(a)

erg.q = 0
PokeL(@erg,a\n[0])
PokeL(@erg+4,a\n[1])

Debug $00000001FFFFFFFE
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(a)
Debug ""

;============================================
;-  BN_SHR()
;============================================
Debug "Testing BN_SHR()"

a\n[0]=$FFFFFFFE
a\n[1]=$00000001

BN_SHR(res, a, 1)

erg.q = 0
PokeL(@erg,res\n[0])
PokeL(@erg+4,res\n[1])

Debug $00000000FFFFFFFF
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(res)
Debug ""


;============================================
;-  BN_SHR1()
;============================================
Debug "Testing BN_SHR1()"

a\n[0]=$FFFFFFFE
a\n[1]=$00000001

BN_SHR1(a)

erg.q = 0
PokeL(@erg,a\n[0])
PokeL(@erg+4,a\n[1])

Debug $00000000FFFFFFFF
Debug StrU(erg,4)
Debug RSet(HexQ(erg),16,"0")
Debug BN_HEX(a)
Debug ""

;============================================
;-  BN_CMP()
;============================================
Debug "Testing BN_CMP()"

a\n[0]=$00000002
a\n[1]=$00000001
b\n[0]=$00000000
b\n[1]=$00000001

For k=0 To 2
 CopyMemory(BN_SUBINT(res, a, 1), @a, SizeOf(BIG_NUMBER))
 Debug "a = "+BN_HEX(a)
 Debug "b = "+BN_HEX(b)
 Debug Space(10)+StringField("a < b,a = b,a > b",2+BN_CMP(a, b),",")
Next
Debug ""

;============================================
;-  BN_CMPINT()
;============================================
Debug "Testing BN_CMPINT()"

a\n[0]=$00000001
a\n[1]=$00000000

For k=0 To 2
 Debug "a = "+BN_HEX(a)
 Debug "b = "+RSet(Hex(k),16,"0")
 Debug Space(10)+StringField("a < b,a = b,a > b",2+BN_CMPINT(a, k),",")
Next
Debug ""

;============================================
;-  BN_IS_EVEN()
;============================================
Debug "Testing BN_IS_EVEN()"

a\n[0]=$00000001
a\n[1]=$00000001
b\n[0]=$00000000
b\n[1]=$00000001

Debug "a is "+StringField("odd,even",1+BN_IS_EVEN(a),",")+" ("+BN_HEX(a)+")"
Debug "b is "+StringField("odd,even",1+BN_IS_EVEN(b),",")+" ("+BN_HEX(b)+")"
Debug ""

;============================================
;-  BN_IS_PRIME()
;============================================
Debug "Testing BN_IS_PRIME()"

a\n[0]=$00001003
a\n[1]=$00000000
b\n[0]=$91DF66CD
b\n[1]=$00000002

Debug "a is "+StringField("not ,",1+BN_IS_PRIME(a),",")+"a prime number ("+BN_STR(a)+")"
Debug "b is "+StringField("not ,",1+BN_IS_PRIME(b),",")+"a prime number ("+BN_HEX(b)+")"
Debug ""

;============================================
;-  BN_NEXT_PRIME()
;============================================
Debug "Testing BN_NEXT_PRIME()"

a\n[0]=$00000000
a\n[1]=$00000001

BN_NEXT_PRIME(b, a)
BN_NEXT_PRIME(c, b)

Debug "a = "+BN_HEX(a)
Debug "b = "+BN_HEX(b)
Debug "c = "+BN_HEX(c)
Debug ""

;============================================
;-  BN_USED_BITS()
;============================================
Debug "Testing BN_USED_BITS()"

a\n[0]=$31654896
a\n[1]=$00000001

Debug "a needs "+Str(BN_USED_BITS(a))+" Bits ("+BN_HEX(a)+")"
Debug ""

;============================================
;-  BN_USED_LONGS()
;============================================
Debug "Testing BN_USED_LONGS()"

a\n[0]=$00000000
a\n[1]=$00000000
b\n[0]=$31654896
b\n[1]=$00000000
c\n[0]=$31654896
c\n[1]=$00000001

Debug "a needs "+Str(BN_USED_LONGS(a))+" Longs ("+BN_HEX(a)+")"
Debug "b needs "+Str(BN_USED_LONGS(b))+" Long ("+BN_HEX(b)+")"
Debug "b needs "+Str(BN_USED_LONGS(c))+" Longs ("+BN_HEX(c)+")"
Debug ""
BigNumbers_test2.pb

Code: Select all

XIncludeFile "BigNumbers.pbi"

#count = 1;100000

Macro _size
 4352*128;1088
EndMacro

InitBigNumbers(_size)

a.BIG_NUMBER
b.BIG_NUMBER
c.BIG_NUMBER
d.BIG_NUMBER

Macro qt()
 "
EndMacro

Macro StartTest(Count)
 Define a__.q
 tt__.q = 0
 For j__ = 1 To 10
  t__.q = ElapsedMilliseconds() & $FFFFFFFF
  For i__ = 1 To Count
EndMacro

Macro StopTest(Name)
  Next
  t__ = (ElapsedMilliseconds() & $FFFFFFFF) - t__
  tt__ + t__
  PrintN(qt()Name: qt() + " " + Str(t__)+"ms")
 Next
 PrintN(qt()Name: qt() + " " + StrD(tt__ / 10, 1)+"ms")
 If a__ = 0
  a__ = tt__
 Else
  PrintN("-> " + StrD(a__ / tt__, 3) + " times faster")
 EndIf
EndMacro

OpenConsole()

BN_RND_MAX(a, _size / 2)
BN_RND_MAX(b, _size / 2)

StartTest(#count)
 BN_MUL(c, a, b)
StopTest(BN_MUL)

StartTest(#count)
 BN_KARATSUBA(d, a, b)
StopTest(BN_KARATSUBA)

Input()
User avatar
idle
Always Here
Always Here
Posts: 5050
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: larger number calculations with positive integers

Post by idle »

thanks it could be very useful.
User avatar
robertfern
User
User
Posts: 23
Joined: Fri Feb 02, 2018 10:33 pm
Location: New Jersey

Re: larger number calculations with positive integers

Post by robertfern »

I cant seem to get this library to compile.

First, the compiler doesn't like the HexQ() function. Says it's deprecated.

Second, the Assembler throws up errors, that i have no idea about.

I'm on High Sierra with PB 5.70
Mac OSX Ventura & Windows 10, PB 6.04
jack
Addict
Addict
Posts: 1336
Joined: Fri Apr 25, 2003 11:10 pm

Re: larger number calculations with positive integers

Post by jack »

@pcfreak
did you know about LibTom? https://www.libtom.net
there's LibTomMath and LibTomCrypt the license is public domain http://unlicense.org/
you will need MS Visual studio to build the library for PureBasic, the only hard part is translating the headers
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: larger number calculations with positive integers

Post by Little John »

Post Reply