Strona główna > C, Rówania modularne > Rówania modularne

Rówania modularne

8 Sierpień 2011 Dodaj komentarz Go to comments
//Modular-Linear-Equation-Solver
// ax = b (mod n) 
//Implementacja w C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void Rozszerzony_Algorytm_Euklidesa(int a, int b, int tab[])
{
    if(a>0 && b>0)
    {
       int a0=a, b0=b;
       int p=1, q=0, r=0, s=1;
       int c,new_r, new_s,quot;
       while (b!=0)
       {  c=a%b;
          quot =(int)floor(a/b);
          a=b;
          b=c;
          new_r=p-quot*r;
          new_s=q-quot*s;
          p=r; q=s;
          r=new_r;
          s=new_s;
       }
    tab[0]=p;
    tab[1]=q;
    tab[2]=((a0*p)+(b0*q));
    printf("\n\nNWD(%d,%d)=%d*%d + %d*%d ", a0, b0, a0, p, b0, q);
    printf(" = %d\n", (a0*p)+(b0*q));
    }
    else printf("Error!");
 }

void RownanieModularne(int a, int b, int n)
{
	int x, _x, _y, d;
	int tab[2];
	Rozszerzony_Algorytm_Euklidesa(a,n,tab);
	_x=tab[0];
	_y=tab[1];
	 d=tab[2];
	if ((b%d)==0)
	{
		x=_x*(b/d)%n;
        printf("\nObliczam wspolczynniki:\n");
        for(int i=0; i<d; i++)
        printf("%d \n", ((x+i*(n/d))%n));
	}
	else printf("Jednak brak rozwiazan :(\n");
}

int main(int argc, char *argv[])
{
  int a,b,n;
  printf("Rowanie modularne postaci:\n");
  printf("ax = b (mod n):\n");
  printf("Podaj a:  ");scanf("%d", &a);
  printf("Podaj b:  ");scanf("%d", &b);
  printf("Podaj n:  ");scanf("%d", &n);
  RownanieModularne(a,b,n);
  system("PAUSE");
  return 0;
}
  1. Brak komentarzy.
  1. 20 Lipiec 2016 o 1:14 pm

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: