matemātika

« previous entry | next entry »
Mar. 26., 2006 | 05:10 am
posted by: elfz in pajautaa

Klusā cerībā, ka kāds te arī bez manis ar ārpusskolas matemātiku saskaras arī dzīvē,

kurā virzienā jārok, vai vismaz kurā mat-literatūrā jāmeklē teorija, lai varētu aprēķināt vienādojumu:

( a * x ) mod b = 1
vai
b - ( a * x ) mod b = 1

jāatrod, attiecīgi x vērtība pie dotajiem a un b. a un b ir čuķ-čuķ par lielu, lai lietotu cirvja metodi (pilno pārlasi).

Konkrēti, šobrīd būtu nepieciešams atrast x pie:
(8bb9f4fh * x) % 4F11B311h = ±1

Kā to paveikt?

# | jā, ir doma! | Add to Memories

Comments {20}

zverj

from: [info]zverj
date: Mar. 26., 2006 - 05:28 am
#

Es vismaz neatceros, ka buutu saskaaries ar mod vienaadojumos. Pietam tas "vai" mani apstulbinaaja. Tas ir tas pats, kas logjiskais "or" vai arii tas ir tikai piemeers?

Tavam variantam es izsecinaaju a mod b = 1 / x

Atbildēt | Diskusija

zverj

from: [info]zverj
date: Mar. 26., 2006 - 05:32 am
#

Pag, mod citi likumi attiecas

Atbildēt | Iepriekšējais | Diskusija

zverj

from: [info]zverj
date: Mar. 26., 2006 - 05:33 am
#

(2 * 3) mod 5 = 1

2 mod 5 = 1 / 3

Nelogjiski

Atbildēt | Iepriekšējais | Diskusija

from: [info]elfz
date: Mar. 26., 2006 - 05:41 am
#

tur tā lieta. (2 * x) mod 5 = 1
x = 3 (vai, x=8, x=13, x=18)
kā lai nosaka šo x. kur lai meklē matemātiku šais gadījumos - to skolā nemācīja (un, esmu pārliecināts, ka nemāca) - kā šo noteikt?

Atbildēt | Iepriekšējais | Diskusija

zverj

from: [info]zverj
date: Mar. 26., 2006 - 05:42 am
#

Modulārā aritmētika izrādās.

Atbildēt | Iepriekšējais | Diskusija

from: [info]elfz
date: Mar. 26., 2006 - 05:44 am
#

yep. būšu mēģināt iebraukt.

Atbildēt | Iepriekšējais

from: [info]elfz
date: Mar. 26., 2006 - 05:37 am
#

"vai" šai gadījumā nozīmē, ka man vajag atrast x, kas apmierinātu vismaz vienu no vienādojumiem - pirmo vienādojumu VAI ARĪ otro.
cik man zināms, matemātiķi ar tamlīdzīgām lietām saskaras sen - piemēram RSA kriptēšana, kas ir kaut kas ļoti līdzīgs, tikai bišķiņ augstāk matemātiskā līmenī.
man vajadzētu pointerus, kurā virzienā rakt un studēt :(

Atbildēt | Iepriekšējais | Diskusija

zverj

from: [info]zverj
date: Mar. 26., 2006 - 05:39 am
#

tikko uzmetu linkus

Atbildēt | Iepriekšējais | Diskusija

from: [info]elfz
date: Mar. 26., 2006 - 05:43 am
#

nu, principā, jāsāk ar http://en.wikipedia.org/wiki/Modular_arithmetic un jārokas tālāk :/

Atbildēt | Iepriekšējais

from: [info]petro
date: Mar. 26., 2006 - 08:01 am
#

Nezinu. Līdzīgos gadījomos es daudz galvu nelauzu, bet lietoju M$Excel pluginu "Solver"

Atbildēt

from: [info]petro
date: Mar. 26., 2006 - 10:11 am
#

principā kad pilnā pārlase ir pārāk apjomīgs darbs pat X GHz procim. Var mēģināt lietot tuvināšanas metodi(iteration). Pats kādreiz vienā programmprojektā esmu izmantojis
Piemērs (ja vari atšifrēt):

procedure GetData(Dp :Integer);
{ Dp - Segas pilns biezums [cm] }

const X :array [1..7] of integer = (0, 30, 60, 90, 120, 150, 180);
      a = 15;
var F   :real; {Force}
    D   :array [1..7] of real;
    K, Ae, r, DeltaR, m, n, dr, Mr, Ep, p :real; {Koeficients, ...}
    AA, BB, CC, D0apr :real;
    kor : real;
    idx : integer;
begin
  K  := 0;
  kor := 128;
  F    := DM.qryFWDimp['F'];
  D[1] := DM.qryFWDimp['D1']/10000;
  D[2] := DM.qryFWDimp['D2']/10000;
  D[3] := DM.qryFWDimp['D3']/10000;
  D[4] := DM.qryFWDimp['D4']/10000;
  D[5] := DM.qryFWDimp['D5']/10000;
  D[6] := DM.qryFWDimp['D6']/10000;
  D[7] := DM.qryFWDimp['D7']/10000;
  repeat
    K := K + Kor;
    Ae := Sqrt( Sqr(a) + Sqr(Dp) * Power(K, 2/3) );
    r  := Ae*0.7;
    DeltaR := r - X[6];
    m := D[6];
    n := D[7];
    for idx := 1 to 5 do
      if  ( X[idx] <= r ) and ( r < x[idx+1] )
      then begin
        DeltaR := r - X[idx];
        m := D[idx];
        n := D[idx+1];
      end;
    dr := m - (m-n)*DeltaR/30;
    Mr := ( 2.4 * F ) / (r * dr);
    Ep := K*Mr;
    p  := (F*10)/(Sqr(a)*Pi);
    AA := 1.5 * a * p;
    BB := Sqrt(1+ Sqr((Dp/a)* Power(Ep/Mr, 1/3)) );
    CC := 1 / Sqrt(1 + Sqr(Dp/a));
    D0apr := AA* (  (1/ (Mr*BB) ) + (1-CC)/Ep );
    kor := Abs(kor/2);
    if D0apr < D[1]
    then kor := -kor;
  until Abs( D[1] - D0apr ) < 0.000005;

  SDNew.S    := DM.qryFWDimp['S'];
  SDNew.Dp   := Dp;
  SDNew.SNef := 0.0093*Dp*Power(Ep, 1/3);
  SDNew.Egr  := Mr/3.3;
end;

Atbildēt | Diskusija

from: [info]petro
date: Mar. 26., 2006 - 10:12 am
#

Tas bija domāts ka jāpavēro mainīgo "K" un "Kor" uzvedība ciklā.

Atbildēt | Iepriekšējais

from: [info]octo
date: Mar. 26., 2006 - 10:55 am
#

Skaitlju teorija :D
Priekshmets pie Bula ieksh LU... bija arii graamatinja... netaa nekad neesmu mekleejis:D

Atbildēt

taapati

from: [info]taapati
date: Mar. 26., 2006 - 11:13 am
#

(a*x) mod b =1, tātad
(a*x-1)mod b = 0, tātad
a*x -1 = k*b, k-koeficients
jeb a*x-b*k=1
sanāk lineārs vjums ar diviem nezināmajiem, kas jāaprēķina veselos skaitļos. To mācēsi izrēķināt? ja kas, varu atsūtīt materiālus, kur parādīts, kā tādus risina, izmantojot Eilera LKD meklēšanas algoritmu. Grūti pateikt, cik ātri strādās, bet, manuprāt, tīri sakarīgā ātrumā :)

Atbildēt

Krišs

from: [info]misame
date: Mar. 26., 2006 - 12:16 pm
#

Manupraat, tavaa uzdevumaa atbilde ir 1270933564.
Vai hex - 4BC0E83C

Kaadreiz LU maacoties kriptograafiju pie Freivalda, biju sataisiijis sev uz JS baazeetu paliigriiku (atronams sheit http://naivist.net/stufi/kripto.htm, darbojas tikai uz IE manupraat).

Taa sadalja, kas saucas "Pretējā elementa meklēšana".
Tur arii kaut kaads izvedums drukaajas aaraa, bet preciizaaku algoru gan tev jaameklee sourcees.

Atbildēt | Diskusija

Krišs

from: [info]misame
date: Mar. 26., 2006 - 12:18 pm
#

Cik pats redzu komentaaraa sourcees, tad tur ir mineets "Lieto Eduarda gudrību un Eilera metodi."
Eduards ir mans kursabiedrs, savukaart Eilera metode laikam ir tas, ko meklee Tu.

Atbildēt | Iepriekšējais

madars

from: [info]madars
date: Mar. 26., 2006 - 02:59 pm
#

1) ja gcd(a,b)=1, tad ar paplašināto Eiklīda algoritmu (angl. - Extended Euclid algorithm) mēs varam izrēķināt tādus x' un y', ka a*x'+b*y'=gcd(a,b)=1, no šejienes arī seko, ka a*x'=1 (mod b).
2) ja gcd(a,b)<>1, tad atrisinājumu nav, jo a*x ir 0 (mod gcd(a,b)), tāpēc arī a*x<>1 (mod k*gcd(a,b)).

Atbildēt | Diskusija

madars

from: [info]madars
date: Mar. 26., 2006 - 07:34 pm
#

nu jā, vēl ir diezgan skaidrs, ka vienādojumam a*x=-1 (mod b) ir atrisinājums tad un tikai tad, ja atrisinājums vienādojumam a*x=1 (mod b). tāpēc vienādojumam a*x=+-1 (mod b) sanāk 0, 1 vai 2 atrisinājumi (pie tam 1 sanāk, ja ax=1 (mod b) un ax=-1 (mod b) => 0=2 (mod b) => b=1 vai b=2).

Atbildēt | Iepriekšējais

Laimī

from: [info]engell
date: Mar. 26., 2006 - 05:16 pm
#

a un b nav 0

Atbildēt