Some questions

[salute2005]

1. Let a and b be relatively prime positive integers with a>b then jacobi's symbol (a/b) can be evaluated using n(([log_2]b)) bit operations.

2.Let [S(j)]^n denote the position of wire in nth section spliced to jth wire of the first section then [S(j)]^n = 1+(j-1).S^(n-1) (mod m) (show)

[matematikator]

Dear friend, where are you gonna use these question...(i only wondered )

Solution2. Sol: i) For n=2 by the rules of the splicing system and [S(j)]^2 = 1+(j-1).S (mod m) so it's true
... ii) Assume [S(j)]^n = 1+(j-1).S^(n-1) (mod m)
... iii) Since we have that the wire in position [S(j)]^n spliced to the wire in position
.... ... [S(j)]^(n+1) = 1+([S(j)]^n -1)S (mod m)
... = 1+(j-1)S^n (mod m)

[matematikator]

....

Solution1: Using(a/b)= (-1)^[s_1(R_1)^2-1)/8+...+s_(n-1).(R_(n-1))^2-1)/8+(R_1 - 1)/2+...+(R_(n-1) - 1)/2], where R_j,s_j are integers for a>b.
Perform a sequence: n(x) divisions such that x=log of b to the base 2. The number of divisions does not exceed the number of divisions needed to find (a,b) using the euclidean algorithm. Thus by Lema's Theorem, use n(x) divisions are needed. Each division can be done using n(x^2) bit operations. So R_j and s_j can be found using n(x) bit operations.
n(x^3) bit operations are required to find the integers R_j,s_j from a and b. The exponent of -1 in the expression for (a/b) by the first theorem will be evaluated using the last three bits in the binarry expznsions of R_j and last bit in the binary expansions of s_j.
Therefore using n(x) additional bit operation to find (a/b). Since
n(x^3)+n(x)=n(x^2)

[salute2005]

Homework!