Специфика использования библиотеки mmath на примере проверки простоты больших чисел

Страницы работы

Содержание работы

ЛЕКЦИЯ №2. 28.02

Специфика использования библиотеки mmath на примере проверки простоты больших чисел.

r – сдвиг на слово.

r b – сдвиг на биты

mmath.h

int Rabin(P, int k);

m_long y;

m_shl (s, rb)

r=(r<<5)+rb

P-1=2r*S

for (i=0; i<k; i++) {

m_rand (x, P[0]-1);

m_blockpowmod(x,S,P,y);

if(m_cmp(y,P-1)||(y[0]!=1))

for(int y=1; j<r, j++){

m_sqr(y, y);

m_div(y,P,m,y)

if (m_cmp==0) break;}

if (j=r) return 1;}

int DivTest(m_long P, int b)

P[0]=Q[0]=32;

{

m_rand (P, P[0]); P[1]!=1;

while (DivTest(P, P[0])||Rabin (P,60));

}

Вариант реализации теста Рабина-Миллера для массива простых чисел от 0 до 65519.

#include <merror.h>

#include <MMATH.h>

#include <MDEF.h>

#include <DivTest.h>

#include <iostream.h>

#define PRIME_2BYTE (6542) // количество двухбайтовых простых чисел

#define PRIME_1BYTE (54)

#pragma hdrstop

int Rabin(M_LONG P, int toc);

int DivTest(M_LONG P,unsigned char num);

#pragma argsused

int main(int argc, char* argv[])

{   int non;

unsigned long Prime[]={2L,3L,5L,7L,11L,13L,17L,19L,23L,29L,31L,

37L,41L,43L,47L,53L,59L,61L,67L,71L,73L, 79L,83L,89L,97L,101L,103L, 107L,109L,113L,127L, 131L,137L,139L,………………………………………..

………………………………………………………………………….. ,65519L,

65521L};

srand(time(NULL));

M_LONG       P={1,24313};

if(DivTest(P,100))

return 1;

 non=Rabin(P,60);

 cout<<non;

  cin>>non;

        return 0;

}

 int Rabin(M_LONG P, int toc){

 M_LONG  P_1, a, temp, s, temp1,temp2, temp3, temp4;

 M_LONG one={1,1};

   int y=0, rb=0, t, t1=0;

   m_copy(P_1,P);

 P_1[1]&=0xFFFFFFFE;

  for (unsigned int i=1;i<=P_1[0];i++){

        if(P_1[i]==0)

         y++;

        else break;}

        temp[0]=P_1[0]-y;

        for (int j=1; j<=temp[0];j++)

        temp[j]=P_1[y+j];

        for (unsigned long mask=1;(temp[1]&mask)==0;){

        mask=mask<<1;

        rb++;}

        t=y*32+rb;

   m_shr(temp,t);

   int j=0;

   for (int k=0;k<toc;k++){

   m_rand(a,P[0]);

   m_blockmontpowmod(a,temp,P,temp1);

   if ((m_cmp(temp1,one))*(m_cmp(temp1,P_1))!=0){

       for (j=1;j<t;j++){

        m_sqr(temp1,temp2);

        m_div(temp2, P, temp3, temp1);

        if (m_cmp(temp1,P_1)==0)

                break;}

        if (j==t)

        return 1;

        }      }

     return 0; }

     int DivTest(M_LONG P,unsigned char num){

            register int i;

            M_LONG q;

            DIGIT rem;

            num=(num==2)?PRIME_2BYTE:PRIME_1BYTE;

            for(i=0;i<num;i++){

                        m_div1(P,Prime[i],q,&rem);//rem-остаток

                        if(rem==0)// делится нацело

                                    return 1;

                        if(P[0]==1 && P[1]<=Prime[i])

                                    return 0;}

            return 0;}

ЛЕКЦИЯ 3. 3.03

Реализация простейших арифметических операций для целочисленного деления

X=(x1…xn)B

Y=(y1…yk)B

Z=(z1…zm)B

for (i=0; c=0; i<n; i++){

ri=(xi-yi+c+B) mod B;

c=[(xi-yi+c+B)/B]

}

1. Метод умножения со сканированием операнда

2. Метод умножения со сканированием произведения.

B=2w

X=(xn …x2, x1)B

Y=(yt…y2, y1)B

Z=(zn+t…z2, z1)B

For (i=1; i<=n+t; i++) zi=0 //обнуляем

     For (i=1; i<=n; i++) {      //по xi

     u=0;

            for (j=1; j<t; j++){    //по yi

(u,v)B ← Zi+j-1+xi*yi

//операция внутреннего произведения

Zi+j-1=V

//

Zi+j-1=u;

}  //for ;

Пример:

b=10, n=2, t=3

n+t=5;

x=(89)b

y=(769)b

i

j

u

Zi+j-1+xiyi+u

Z5

Z4

Z3

Z2

Z1

u*v

1

1

0

0+9*9+0

0

0

0

0

1

81

2

8

0+9*6+8=62

0

0

0

2

1

62

3

6

0+9*7+6=69

0

6

9

2

1

69

2

1

0

2+8*9+0=74

0

6

9

4

1

72

2

7

9+8*6+7=64

0

6

4

4

1

64

3

6

6+8*7+6=68

6

8

4

4

1

68

(r2 r1 r0)B←(0,0,0)

for (k=1; k<2t; k++){

(i,j)/i+j=k;   0≤i,j≤t}

(u,v) ←xi yi

(c1 r0)←r0 w //бит переноса

(c1 r1)←ri+u+c //бит с учетом переноса
r2=r2+c

rk=r0, r0=r1, r1=r2, r2=0

r2t=r0

 

Метод Карацубы

      56           56 

 
224                                                                                 224

                                                                                                                      9 “*” по 64

                                                                                                                       3“*” по 32

                        12 “*” 64 бита

|X|B=t

|Z|=2t

for (i=1; i<=2t; i++) z=0

for (i=1; i<=t; i++){(u v)B←rℓi-1+xi2

z2i-1=v, c=u

for (j=i+1; j<=t; j++){

(u v)B←ri+j-1+2x : yi+ci

zi+j-1=v, c=u

            zi+t-1=u

t2+t/2

}}


ЛЕКЦИЯ 4. 3.03

Изучение специфики представления функций библиотеки miracl

  1. Арифметика больших целых чисел Big
  2. Арифметика больших дробных чисел Flash
  3. Арифметика ЭК E(Fp)

     E(F2m)

  1. AES.
  2. SHA – 160 бит.

  X[1]

Похожие материалы

Информация о работе