) of length 3, Bobo defines their product as. begin{matrix} v_1^{e_{1, 1}} times dots times v_n^{e_{1, n}} \ dots \ v_1^{e_{q, 1}} times dots times v_n^{e_{q, n}} end{matrix}. The vectors and integers are generated given parameters
Let P = 998244353, for two vectors (a_0, a_1, a_2) (a ,a 1 ,a 2 ), (b_0, b_1, b_2) (b ,b 1 ,b 2 ) of length 3, Bobo defines their (multiplicative) product as (a_0, a_1, a_2) times (b_0, b_1, b_2) \ = ( (a_0 b_0 + a_1 b_2 + a_2 b_1) bmod P, \ (a_1 b_0 + a_2 b_2 + a_0 b_1) bmod P, \ (a_2 b_0 + a_0 b_2 + a_1 b_1) bmod P ). (a ,a 1 ,a 2 )×(b ,b 1 ,b 2 ) =((a b +a 1 b 2 +a 2 b 1 )modP, (a 1 b +a 2 b 2 +a b 1 )modP, (a 2 b +a b 2 +a 1 b 1 )modP). Given n 3-vectors v_1, dots, v_n v 1 ,…,v n and q cdot n q⋅n integers e_{i, 1}, dots, e_{i, n} e i,1 ,…,e i,n , he would like to compute q products, which are begin{matrix} v_1^{e_{1, 1}} times dots times v_n^{e_{1, n}} \ dots \ v_1^{e_{q, 1}} times dots times v_n^{e_{q, n}} end{matrix} v 1 e 1,1 ×⋯×v n e 1,n … v 1 e q,1 ×⋯×v n e q,n The vectors and integers are generated given parameters m, z_0, a, b m,z ,a,b by the following codes: z = z0 for i in 1..n for j in 0..2 z = (z * a + b) mod 2^32 v[i][j] = z mod P for k in 1..q for i in 1..n e[k][i] = 0 for j in 0..(m - 1) z = (z * a + b) mod 2^32 e[k][i] += z * 2^{32 * j}
