Generated by Cython 0.14.1 on Fri Jul 22 18:51:54 2011
Raw output: _home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.c
1:
2: include "interrupt.pxi" # ctrl-c interrupt block support
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":2 * * include "interrupt.pxi" # ctrl-c interrupt block support #<<<<<<<<<<<<<<* include "stdsage.pxi" # ctrl-c interrupt block support * */ __pyx_t_2 = PyDict_New(); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 2; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(((PyObject *)__pyx_t_2)); if (PyObject_SetAttr(__pyx_m, __pyx_n_s____test__, ((PyObject *)__pyx_t_2))<0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 2; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0;
3: include "stdsage.pxi" # ctrl-c interrupt block support
4:
5: include "cdefs.pxi"
6: include 'sage/libs/pari/decl.pxi'
7:
8: from sage.libs.pari.gen import pari
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":8 * include 'sage/libs/pari/decl.pxi' * * from sage.libs.pari.gen import pari #<<<<<<<<<<<<<<* from libc.stdint cimport uint8_t, uint_fast8_t, uint32_t, uint_fast32_t, uint_fast64_t * */ __pyx_t_1 = PyList_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(((PyObject *)__pyx_t_1)); __Pyx_INCREF(((PyObject *)__pyx_n_s__pari)); PyList_SET_ITEM(__pyx_t_1, 0, ((PyObject *)__pyx_n_s__pari)); __Pyx_GIVEREF(((PyObject *)__pyx_n_s__pari)); __pyx_t_2 = __Pyx_Import(((PyObject *)__pyx_n_s_2), ((PyObject *)__pyx_t_1)); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_2); __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; __pyx_t_1 = PyObject_GetAttr(__pyx_t_2, __pyx_n_s__pari); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_1); if (PyObject_SetAttr(__pyx_m, __pyx_n_s__pari, __pyx_t_1)<0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
9: from libc.stdint cimport uint8_t, uint_fast8_t, uint32_t, uint_fast32_t, uint_fast64_t
10:
11: cdef extern from "pari/pari.h":
12: cdef void NEXT_PRIME_VIADIFF(uint32_t, uint_fast8_t *)
13:
14: cdef uint_fast32_t[32] shiftTab
15: shiftTab[ 0] = 0x00000001u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":15 * * cdef uint_fast32_t[32] shiftTab * shiftTab[ 0] = 0x00000001u #<<<<<<<<<<<<<<* shiftTab[ 1] = 0x00000002u * shiftTab[ 2] = 0x00000004u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[0]) = 0x00000001U;
16: shiftTab[ 1] = 0x00000002u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":16 * cdef uint_fast32_t[32] shiftTab * shiftTab[ 0] = 0x00000001u * shiftTab[ 1] = 0x00000002u #<<<<<<<<<<<<<<* shiftTab[ 2] = 0x00000004u * shiftTab[ 3] = 0x00000008u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[1]) = 0x00000002U;
17: shiftTab[ 2] = 0x00000004u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":17 * shiftTab[ 0] = 0x00000001u * shiftTab[ 1] = 0x00000002u * shiftTab[ 2] = 0x00000004u #<<<<<<<<<<<<<<* shiftTab[ 3] = 0x00000008u * shiftTab[ 4] = 0x00000010u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[2]) = 0x00000004U;
18: shiftTab[ 3] = 0x00000008u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":18 * shiftTab[ 1] = 0x00000002u * shiftTab[ 2] = 0x00000004u * shiftTab[ 3] = 0x00000008u #<<<<<<<<<<<<<<* shiftTab[ 4] = 0x00000010u * shiftTab[ 5] = 0x00000020u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[3]) = 0x00000008U;
19: shiftTab[ 4] = 0x00000010u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":19 * shiftTab[ 2] = 0x00000004u * shiftTab[ 3] = 0x00000008u * shiftTab[ 4] = 0x00000010u #<<<<<<<<<<<<<<* shiftTab[ 5] = 0x00000020u * shiftTab[ 6] = 0x00000040u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[4]) = 0x00000010U;
20: shiftTab[ 5] = 0x00000020u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":20 * shiftTab[ 3] = 0x00000008u * shiftTab[ 4] = 0x00000010u * shiftTab[ 5] = 0x00000020u #<<<<<<<<<<<<<<* shiftTab[ 6] = 0x00000040u * shiftTab[ 7] = 0x00000080u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[5]) = 0x00000020U;
21: shiftTab[ 6] = 0x00000040u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":21 * shiftTab[ 4] = 0x00000010u * shiftTab[ 5] = 0x00000020u * shiftTab[ 6] = 0x00000040u #<<<<<<<<<<<<<<* shiftTab[ 7] = 0x00000080u * shiftTab[ 8] = 0x00000100u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[6]) = 0x00000040U;
22: shiftTab[ 7] = 0x00000080u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":22 * shiftTab[ 5] = 0x00000020u * shiftTab[ 6] = 0x00000040u * shiftTab[ 7] = 0x00000080u #<<<<<<<<<<<<<<* shiftTab[ 8] = 0x00000100u * shiftTab[ 9] = 0x00000200u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[7]) = 0x00000080U;
23: shiftTab[ 8] = 0x00000100u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":23 * shiftTab[ 6] = 0x00000040u * shiftTab[ 7] = 0x00000080u * shiftTab[ 8] = 0x00000100u #<<<<<<<<<<<<<<* shiftTab[ 9] = 0x00000200u * shiftTab[10] = 0x00000400u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[8]) = 0x00000100U;
24: shiftTab[ 9] = 0x00000200u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":24 * shiftTab[ 7] = 0x00000080u * shiftTab[ 8] = 0x00000100u * shiftTab[ 9] = 0x00000200u #<<<<<<<<<<<<<<* shiftTab[10] = 0x00000400u * shiftTab[11] = 0x00000800u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[9]) = 0x00000200U;
25: shiftTab[10] = 0x00000400u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":25 * shiftTab[ 8] = 0x00000100u * shiftTab[ 9] = 0x00000200u * shiftTab[10] = 0x00000400u #<<<<<<<<<<<<<<* shiftTab[11] = 0x00000800u * shiftTab[12] = 0x00001000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[10]) = 0x00000400U;
26: shiftTab[11] = 0x00000800u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":26 * shiftTab[ 9] = 0x00000200u * shiftTab[10] = 0x00000400u * shiftTab[11] = 0x00000800u #<<<<<<<<<<<<<<* shiftTab[12] = 0x00001000u * shiftTab[13] = 0x00002000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[11]) = 0x00000800U;
27: shiftTab[12] = 0x00001000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":27 * shiftTab[10] = 0x00000400u * shiftTab[11] = 0x00000800u * shiftTab[12] = 0x00001000u #<<<<<<<<<<<<<<* shiftTab[13] = 0x00002000u * shiftTab[14] = 0x00004000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[12]) = 0x00001000U;
28: shiftTab[13] = 0x00002000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":28 * shiftTab[11] = 0x00000800u * shiftTab[12] = 0x00001000u * shiftTab[13] = 0x00002000u #<<<<<<<<<<<<<<* shiftTab[14] = 0x00004000u * shiftTab[15] = 0x00008000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[13]) = 0x00002000U;
29: shiftTab[14] = 0x00004000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":29 * shiftTab[12] = 0x00001000u * shiftTab[13] = 0x00002000u * shiftTab[14] = 0x00004000u #<<<<<<<<<<<<<<* shiftTab[15] = 0x00008000u * shiftTab[16] = 0x00010000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[14]) = 0x00004000U;
30: shiftTab[15] = 0x00008000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":30 * shiftTab[13] = 0x00002000u * shiftTab[14] = 0x00004000u * shiftTab[15] = 0x00008000u #<<<<<<<<<<<<<<* shiftTab[16] = 0x00010000u * shiftTab[17] = 0x00020000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[15]) = 0x00008000U;
31: shiftTab[16] = 0x00010000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":31 * shiftTab[14] = 0x00004000u * shiftTab[15] = 0x00008000u * shiftTab[16] = 0x00010000u #<<<<<<<<<<<<<<* shiftTab[17] = 0x00020000u * shiftTab[18] = 0x00040000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[16]) = 0x00010000U;
32: shiftTab[17] = 0x00020000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":32 * shiftTab[15] = 0x00008000u * shiftTab[16] = 0x00010000u * shiftTab[17] = 0x00020000u #<<<<<<<<<<<<<<* shiftTab[18] = 0x00040000u * shiftTab[19] = 0x00080000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[17]) = 0x00020000U;
33: shiftTab[18] = 0x00040000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":33 * shiftTab[16] = 0x00010000u * shiftTab[17] = 0x00020000u * shiftTab[18] = 0x00040000u #<<<<<<<<<<<<<<* shiftTab[19] = 0x00080000u * shiftTab[20] = 0x00100000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[18]) = 0x00040000U;
34: shiftTab[19] = 0x00080000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":34 * shiftTab[17] = 0x00020000u * shiftTab[18] = 0x00040000u * shiftTab[19] = 0x00080000u #<<<<<<<<<<<<<<* shiftTab[20] = 0x00100000u * shiftTab[21] = 0x00200000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[19]) = 0x00080000U;
35: shiftTab[20] = 0x00100000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":35 * shiftTab[18] = 0x00040000u * shiftTab[19] = 0x00080000u * shiftTab[20] = 0x00100000u #<<<<<<<<<<<<<<* shiftTab[21] = 0x00200000u * shiftTab[22] = 0x00400000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[20]) = 0x00100000U;
36: shiftTab[21] = 0x00200000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":36 * shiftTab[19] = 0x00080000u * shiftTab[20] = 0x00100000u * shiftTab[21] = 0x00200000u #<<<<<<<<<<<<<<* shiftTab[22] = 0x00400000u * shiftTab[23] = 0x00800000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[21]) = 0x00200000U;
37: shiftTab[22] = 0x00400000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":37 * shiftTab[20] = 0x00100000u * shiftTab[21] = 0x00200000u * shiftTab[22] = 0x00400000u #<<<<<<<<<<<<<<* shiftTab[23] = 0x00800000u * shiftTab[24] = 0x01000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[22]) = 0x00400000U;
38: shiftTab[23] = 0x00800000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":38 * shiftTab[21] = 0x00200000u * shiftTab[22] = 0x00400000u * shiftTab[23] = 0x00800000u #<<<<<<<<<<<<<<* shiftTab[24] = 0x01000000u * shiftTab[25] = 0x02000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[23]) = 0x00800000U;
39: shiftTab[24] = 0x01000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":39 * shiftTab[22] = 0x00400000u * shiftTab[23] = 0x00800000u * shiftTab[24] = 0x01000000u #<<<<<<<<<<<<<<* shiftTab[25] = 0x02000000u * shiftTab[26] = 0x04000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[24]) = 0x01000000U;
40: shiftTab[25] = 0x02000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":40 * shiftTab[23] = 0x00800000u * shiftTab[24] = 0x01000000u * shiftTab[25] = 0x02000000u #<<<<<<<<<<<<<<* shiftTab[26] = 0x04000000u * shiftTab[27] = 0x08000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[25]) = 0x02000000U;
41: shiftTab[26] = 0x04000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":41 * shiftTab[24] = 0x01000000u * shiftTab[25] = 0x02000000u * shiftTab[26] = 0x04000000u #<<<<<<<<<<<<<<* shiftTab[27] = 0x08000000u * shiftTab[28] = 0x10000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[26]) = 0x04000000U;
42: shiftTab[27] = 0x08000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":42 * shiftTab[25] = 0x02000000u * shiftTab[26] = 0x04000000u * shiftTab[27] = 0x08000000u #<<<<<<<<<<<<<<* shiftTab[28] = 0x10000000u * shiftTab[29] = 0x20000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[27]) = 0x08000000U;
43: shiftTab[28] = 0x10000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":43 * shiftTab[26] = 0x04000000u * shiftTab[27] = 0x08000000u * shiftTab[28] = 0x10000000u #<<<<<<<<<<<<<<* shiftTab[29] = 0x20000000u * shiftTab[30] = 0x40000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[28]) = 0x10000000U;
44: shiftTab[29] = 0x20000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":44 * shiftTab[27] = 0x08000000u * shiftTab[28] = 0x10000000u * shiftTab[29] = 0x20000000u #<<<<<<<<<<<<<<* shiftTab[30] = 0x40000000u * shiftTab[31] = 0x80000000u */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[29]) = 0x20000000U;
45: shiftTab[30] = 0x40000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":45 * shiftTab[28] = 0x10000000u * shiftTab[29] = 0x20000000u * shiftTab[30] = 0x40000000u #<<<<<<<<<<<<<<* shiftTab[31] = 0x80000000u * */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[30]) = 0x40000000U;
46: shiftTab[31] = 0x80000000u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":46 * shiftTab[29] = 0x20000000u * shiftTab[30] = 0x40000000u * shiftTab[31] = 0x80000000u #<<<<<<<<<<<<<<* * cdef uint_fast8_t[256] twoDiv */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[31]) = 0x80000000U;
47:
48: cdef uint_fast8_t[256] twoDiv
49: cdef uint_fast32_t tempItr, tempVar
50:
51: twoDiv[0] = 8u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":51 * cdef uint_fast32_t tempItr, tempVar * * twoDiv[0] = 8u #<<<<<<<<<<<<<<* for tempItr in range(1,255u): * tempVar = tempItr */ (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_twoDiv[0]) = 8U;
52: for tempItr in range(1,255u):
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":52 * * twoDiv[0] = 8u * for tempItr in range(1,255u): #<<<<<<<<<<<<<<* tempVar = tempItr * while not tempVar&1u: */ for (__pyx_t_3 = 1; __pyx_t_3<255U; __pyx_t_3+=1) { __pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_tempItr = __pyx_t_3;
53: tempVar = tempItr
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":53
* twoDiv[0] = 8u
* for tempItr in range(1,255u):
* tempVar = tempItr # <<<<<<<<<<<<<<
* while not tempVar&1u:
* twoDiv[tempItr] += 1u
*/
__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_tempVar = __pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_tempItr;
54: while not tempVar&1u:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":54
* for tempItr in range(1,255u):
* tempVar = tempItr
* while not tempVar&1u: # <<<<<<<<<<<<<<
* twoDiv[tempItr] += 1u
* tempVar >>= 1u
*/
while (1) {
__pyx_t_4 = (!(__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_tempVar & 1U));
if (!__pyx_t_4) break;
55: twoDiv[tempItr] += 1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":55
* tempVar = tempItr
* while not tempVar&1u:
* twoDiv[tempItr] += 1u # <<<<<<<<<<<<<<
* tempVar >>= 1u
*
*/
__pyx_t_5 = __pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_tempItr;
(__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_twoDiv[__pyx_t_5]) = ((__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_twoDiv[__pyx_t_5]) + 1U);
56: tempVar >>= 1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":56
* while not tempVar&1u:
* twoDiv[tempItr] += 1u
* tempVar >>= 1u # <<<<<<<<<<<<<<
*
* cdef uint_fast32_t exp_mod(uint_fast64_t b, uint_fast32_t e, uint_fast32_t p):
*/
__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_tempVar = (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_tempVar >> 1U);
}
}
57:
58: cdef uint_fast32_t exp_mod(uint_fast64_t b, uint_fast32_t e, uint_fast32_t p):
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":58 * tempVar >>= 1u * * cdef uint_fast32_t exp_mod(uint_fast64_t b, uint_fast32_t e, uint_fast32_t p): #<<<<<<<<<<<<<<* cdef uint_fast64_t q * if e&1u: q = b */ static uint_fast32_t __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(uint_fast64_t __pyx_v_b, uint_fast32_t __pyx_v_e, uint_fast32_t __pyx_v_p) { uint_fast64_t __pyx_v_q; uint_fast32_t __pyx_r; __Pyx_RefNannySetupContext("exp_mod");
59: cdef uint_fast64_t q
60: if e&1u: q = b
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":60 * cdef uint_fast32_t exp_mod(uint_fast64_t b, uint_fast32_t e, uint_fast32_t p): * cdef uint_fast64_t q * if e&1u: q = b #<<<<<<<<<<<<<<* else: q = 1ull * e >>= 1u */ __pyx_t_1 = (__pyx_v_e & 1U); if (__pyx_t_1) { __pyx_v_q = __pyx_v_b; goto __pyx_L3; } /*else*/ {
61: else: q = 1ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":61
* cdef uint_fast64_t q
* if e&1u: q = b
* else: q = 1ull # <<<<<<<<<<<<<<
* e >>= 1u
* while e:
*/
__pyx_v_q = 1ULL;
}
__pyx_L3:;
62: e >>= 1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":62 * if e&1u: q = b * else: q = 1ull * e >>= 1u #<<<<<<<<<<<<<<* while e: * b *= b */ __pyx_v_e = (__pyx_v_e >> 1U);
63: while e:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":63 * else: q = 1ull * e >>= 1u * while e: #<<<<<<<<<<<<<<* b *= b * if b > 4294967295ull: b %= p */ while (1) { if (!__pyx_v_e) break;
64: b *= b
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":64
* e >>= 1u
* while e:
* b *= b # <<<<<<<<<<<<<<
* if b > 4294967295ull: b %= p
* if e&1u:
*/
__pyx_v_b = (__pyx_v_b * __pyx_v_b);
65: if b > 4294967295ull: b %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":65
* while e:
* b *= b
* if b > 4294967295ull: b %= p # <<<<<<<<<<<<<<
* if e&1u:
* q *= b
*/
__pyx_t_2 = (__pyx_v_b > 4294967295ULL);
if (__pyx_t_2) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 65; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_b = (__pyx_v_b % __pyx_v_p);
goto __pyx_L6;
}
__pyx_L6:;
66: if e&1u:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":66
* b *= b
* if b > 4294967295ull: b %= p
* if e&1u: # <<<<<<<<<<<<<<
* q *= b
* if q > 4294967295ull: q %= p
*/
__pyx_t_1 = (__pyx_v_e & 1U);
if (__pyx_t_1) {
67: q *= b
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":67
* if b > 4294967295ull: b %= p
* if e&1u:
* q *= b # <<<<<<<<<<<<<<
* if q > 4294967295ull: q %= p
* e >>= 1u
*/
__pyx_v_q = (__pyx_v_q * __pyx_v_b);
68: if q > 4294967295ull: q %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":68
* if e&1u:
* q *= b
* if q > 4294967295ull: q %= p # <<<<<<<<<<<<<<
* e >>= 1u
* if q > 4294967295ull: q %= p
*/
__pyx_t_2 = (__pyx_v_q > 4294967295ULL);
if (__pyx_t_2) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_q = (__pyx_v_q % __pyx_v_p);
goto __pyx_L8;
}
__pyx_L8:;
goto __pyx_L7;
}
__pyx_L7:;
69: e >>= 1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":69
* q *= b
* if q > 4294967295ull: q %= p
* e >>= 1u # <<<<<<<<<<<<<<
* if q > 4294967295ull: q %= p
* return q
*/
__pyx_v_e = (__pyx_v_e >> 1U);
}
70: if q > 4294967295ull: q %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":70 * if q > 4294967295ull: q %= p * e >>= 1u * if q > 4294967295ull: q %= p #<<<<<<<<<<<<<<* return q * */ __pyx_t_2 = (__pyx_v_q > 4294967295ULL); if (__pyx_t_2) { if (unlikely(__pyx_v_p == 0)) { PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero"); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 70; __pyx_clineno = __LINE__; goto __pyx_L1_error;} } __pyx_v_q = (__pyx_v_q % __pyx_v_p); goto __pyx_L9; } __pyx_L9:;
71: return q
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":71 * e >>= 1u * if q > 4294967295ull: q %= p * return q #<<<<<<<<<<<<<<* * cdef uint_fast32_t non_residue(uint_fast32_t p): */ __pyx_r = __pyx_v_q; goto __pyx_L0; __pyx_r = 0; goto __pyx_L0; __pyx_L1_error:; __Pyx_WriteUnraisable("_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.exp_mod"); __pyx_r = 0; __pyx_L0:; __Pyx_RefNannyFinishContext(); return __pyx_r; }
72:
73: cdef uint_fast32_t non_residue(uint_fast32_t p):
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":73 * return q * * cdef uint_fast32_t non_residue(uint_fast32_t p): #<<<<<<<<<<<<<<* cdef uint8_t *pariPrimePtr =<uint8_t *>diffptr * cdef uint32_t pariP = 0u */ static uint_fast32_t __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_non_residue(uint_fast32_t __pyx_v_p) { uint8_t *__pyx_v_pariPrimePtr; uint32_t __pyx_v_pariP; uint_fast32_t __pyx_r; __Pyx_RefNannySetupContext("non_residue");
74: cdef uint8_t *pariPrimePtr = <uint8_t *>diffptr
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":74 * * cdef uint_fast32_t non_residue(uint_fast32_t p): * cdef uint8_t *pariPrimePtr =<uint8_t *>diffptr #<<<<<<<<<<<<<<* cdef uint32_t pariP = 0u * NEXT_PRIME_VIADIFF(pariP, pariPrimePtr) */ __pyx_v_pariPrimePtr = ((uint8_t *)diffptr);
75: cdef uint32_t pariP = 0u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":75 * cdef uint_fast32_t non_residue(uint_fast32_t p): * cdef uint8_t *pariPrimePtr =<uint8_t *>diffptr * cdef uint32_t pariP = 0u #<<<<<<<<<<<<<<* NEXT_PRIME_VIADIFF(pariP, pariPrimePtr) * while True: */ __pyx_v_pariP = 0U;
76: NEXT_PRIME_VIADIFF(pariP, pariPrimePtr)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":76 * cdef uint8_t *pariPrimePtr =<uint8_t *>diffptr * cdef uint32_t pariP = 0u * NEXT_PRIME_VIADIFF(pariP, pariPrimePtr) #<<<<<<<<<<<<<<* while True: * NEXT_PRIME_VIADIFF(pariP, pariPrimePtr) */ NEXT_PRIME_VIADIFF(__pyx_v_pariP, __pyx_v_pariPrimePtr);
77: while True:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":77 * cdef uint32_t pariP = 0u * NEXT_PRIME_VIADIFF(pariP, pariPrimePtr) * while True: #<<<<<<<<<<<<<<* NEXT_PRIME_VIADIFF(pariP, pariPrimePtr) * if exp_mod(p,(pariP-1u)>>1u,pariP)%pariP > 1u: */ while (1) { if (!1) break;
78: NEXT_PRIME_VIADIFF(pariP, pariPrimePtr)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":78
* NEXT_PRIME_VIADIFF(pariP, pariPrimePtr)
* while True:
* NEXT_PRIME_VIADIFF(pariP, pariPrimePtr) # <<<<<<<<<<<<<<
* if exp_mod(p,(pariP-1u)>>1u,pariP)%pariP > 1u:
* return pariP
*/
NEXT_PRIME_VIADIFF(__pyx_v_pariP, __pyx_v_pariPrimePtr);
79: if exp_mod(p,(pariP-1u)>>1u,pariP)%pariP > 1u:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":79
* while True:
* NEXT_PRIME_VIADIFF(pariP, pariPrimePtr)
* if exp_mod(p,(pariP-1u)>>1u,pariP)%pariP > 1u: # <<<<<<<<<<<<<<
* return pariP
*
*/
__pyx_t_1 = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(__pyx_v_p, ((__pyx_v_pariP - 1U) >> 1U), __pyx_v_pariP);
if (unlikely(__pyx_v_pariP == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 79; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_t_2 = ((__pyx_t_1 % __pyx_v_pariP) > 1U);
if (__pyx_t_2) {
80: return pariP
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":80
* NEXT_PRIME_VIADIFF(pariP, pariPrimePtr)
* if exp_mod(p,(pariP-1u)>>1u,pariP)%pariP > 1u:
* return pariP # <<<<<<<<<<<<<<
*
* cdef uint_fast32_t sqrt5_mod(uint_fast32_t p):
*/
__pyx_r = __pyx_v_pariP;
goto __pyx_L0;
goto __pyx_L5;
}
__pyx_L5:;
}
__pyx_r = 0;
goto __pyx_L0;
__pyx_L1_error:;
__Pyx_WriteUnraisable("_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.non_residue");
__pyx_r = 0;
__pyx_L0:;
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
81:
82: cdef uint_fast32_t sqrt5_mod(uint_fast32_t p):
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":82 * return pariP * * cdef uint_fast32_t sqrt5_mod(uint_fast32_t p): #<<<<<<<<<<<<<<* if p&3u == 3u: return exp_mod(5ull, (p+1u)>>2u, p)%p * cdef uint_fast64_t q, z */ static uint_fast32_t __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_sqrt5_mod(uint_fast32_t __pyx_v_p) { uint_fast64_t __pyx_v_q; uint_fast64_t __pyx_v_z; uint_fast32_t __pyx_v_d; uint_fast32_t __pyx_v_dp; uint_fast8_t __pyx_v_r; uint_fast64_t __pyx_v_v; uint_fast64_t __pyx_v_res; uint_fast8_t __pyx_v_m; uint_fast32_t __pyx_r; __Pyx_RefNannySetupContext("sqrt5_mod");
83: if p&3u == 3u: return exp_mod(5ull, (p+1u)>>2u, p)%p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":83 * * cdef uint_fast32_t sqrt5_mod(uint_fast32_t p): * if p&3u == 3u: return exp_mod(5ull, (p+1u)>>2u, p)%p #<<<<<<<<<<<<<<* cdef uint_fast64_t q, z * if p&7u == 5u: */ __pyx_t_1 = ((__pyx_v_p & 3U) == 3U); if (__pyx_t_1) { __pyx_t_2 = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(5ULL, ((__pyx_v_p + 1U) >> 2U), __pyx_v_p); if (unlikely(__pyx_v_p == 0)) { PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero"); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 83; __pyx_clineno = __LINE__; goto __pyx_L1_error;} } __pyx_r = (__pyx_t_2 % __pyx_v_p); goto __pyx_L0; goto __pyx_L3; } __pyx_L3:;
84: cdef uint_fast64_t q, z
85: if p&7u == 5u:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":85 * if p&3u == 3u: return exp_mod(5ull, (p+1u)>>2u, p)%p * cdef uint_fast64_t q, z * if p&7u == 5u: #<<<<<<<<<<<<<<* q = exp_mod(10ull, (p-5u)>>3u, p) * z = q*q */ __pyx_t_1 = ((__pyx_v_p & 7U) == 5U); if (__pyx_t_1) {
86: q = exp_mod(10ull, (p-5u)>>3u, p)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":86
* cdef uint_fast64_t q, z
* if p&7u == 5u:
* q = exp_mod(10ull, (p-5u)>>3u, p) # <<<<<<<<<<<<<<
* z = q*q
* if z > 1844674407370955161ull: z %= p
*/
__pyx_v_q = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(10ULL, ((__pyx_v_p - 5U) >> 3U), __pyx_v_p);
87: z = q*q
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":87
* if p&7u == 5u:
* q = exp_mod(10ull, (p-5u)>>3u, p)
* z = q*q # <<<<<<<<<<<<<<
* if z > 1844674407370955161ull: z %= p
* z *= 10ull
*/
__pyx_v_z = (__pyx_v_q * __pyx_v_q);
88: if z > 1844674407370955161ull: z %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":88
* q = exp_mod(10ull, (p-5u)>>3u, p)
* z = q*q
* if z > 1844674407370955161ull: z %= p # <<<<<<<<<<<<<<
* z *= 10ull
* z -= 1ull
*/
__pyx_t_1 = (__pyx_v_z > 1844674407370955161ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 88; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_z = (__pyx_v_z % __pyx_v_p);
goto __pyx_L5;
}
__pyx_L5:;
89: z *= 10ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":89
* z = q*q
* if z > 1844674407370955161ull: z %= p
* z *= 10ull # <<<<<<<<<<<<<<
* z -= 1ull
* if z > 4294967295ull: z %= p
*/
__pyx_v_z = (__pyx_v_z * 10ULL);
90: z -= 1ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":90
* if z > 1844674407370955161ull: z %= p
* z *= 10ull
* z -= 1ull # <<<<<<<<<<<<<<
* if z > 4294967295ull: z %= p
* q *= 5ull
*/
__pyx_v_z = (__pyx_v_z - 1ULL);
91: if z > 4294967295ull: z %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":91
* z *= 10ull
* z -= 1ull
* if z > 4294967295ull: z %= p # <<<<<<<<<<<<<<
* q *= 5ull
* if q > 4294967295ull: q %= p
*/
__pyx_t_1 = (__pyx_v_z > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 91; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_z = (__pyx_v_z % __pyx_v_p);
goto __pyx_L6;
}
__pyx_L6:;
92: q *= 5ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":92
* z -= 1ull
* if z > 4294967295ull: z %= p
* q *= 5ull # <<<<<<<<<<<<<<
* if q > 4294967295ull: q %= p
* return q*z%p
*/
__pyx_v_q = (__pyx_v_q * 5ULL);
93: if q > 4294967295ull: q %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":93
* if z > 4294967295ull: z %= p
* q *= 5ull
* if q > 4294967295ull: q %= p # <<<<<<<<<<<<<<
* return q*z%p
* cdef uint_fast32_t d, dp
*/
__pyx_t_1 = (__pyx_v_q > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 93; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_q = (__pyx_v_q % __pyx_v_p);
goto __pyx_L7;
}
__pyx_L7:;
94: return q*z%p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":94
* q *= 5ull
* if q > 4294967295ull: q %= p
* return q*z%p # <<<<<<<<<<<<<<
* cdef uint_fast32_t d, dp
* if p&15u == 9u:
*/
__pyx_t_3 = (__pyx_v_q * __pyx_v_z);
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 94; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_r = (__pyx_t_3 % __pyx_v_p);
goto __pyx_L0;
goto __pyx_L4;
}
__pyx_L4:;
95: cdef uint_fast32_t d, dp
96: if p&15u == 9u:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":96 * return q*z%p * cdef uint_fast32_t d, dp * if p&15u == 9u: #<<<<<<<<<<<<<<* q = exp_mod(10ull, (p-9u)>>4u, p) * if q > 4294967295ull: q %= p */ __pyx_t_1 = ((__pyx_v_p & 15U) == 9U); if (__pyx_t_1) {
97: q = exp_mod(10ull, (p-9u)>>4u, p)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":97
* cdef uint_fast32_t d, dp
* if p&15u == 9u:
* q = exp_mod(10ull, (p-9u)>>4u, p) # <<<<<<<<<<<<<<
* if q > 4294967295ull: q %= p
* z = q*q
*/
__pyx_v_q = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(10ULL, ((__pyx_v_p - 9U) >> 4U), __pyx_v_p);
98: if q > 4294967295ull: q %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":98
* if p&15u == 9u:
* q = exp_mod(10ull, (p-9u)>>4u, p)
* if q > 4294967295ull: q %= p # <<<<<<<<<<<<<<
* z = q*q
* if z > 1844674407370955161ull: z %= p
*/
__pyx_t_1 = (__pyx_v_q > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 98; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_q = (__pyx_v_q % __pyx_v_p);
goto __pyx_L9;
}
__pyx_L9:;
99: z = q*q
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":99
* q = exp_mod(10ull, (p-9u)>>4u, p)
* if q > 4294967295ull: q %= p
* z = q*q # <<<<<<<<<<<<<<
* if z > 1844674407370955161ull: z %= p
* z *= 10ull
*/
__pyx_v_z = (__pyx_v_q * __pyx_v_q);
100: if z > 1844674407370955161ull: z %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":100
* if q > 4294967295ull: q %= p
* z = q*q
* if z > 1844674407370955161ull: z %= p # <<<<<<<<<<<<<<
* z *= 10ull
* if z > 4294967295ull: z %= p
*/
__pyx_t_1 = (__pyx_v_z > 1844674407370955161ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 100; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_z = (__pyx_v_z % __pyx_v_p);
goto __pyx_L10;
}
__pyx_L10:;
101: z *= 10ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":101
* z = q*q
* if z > 1844674407370955161ull: z %= p
* z *= 10ull # <<<<<<<<<<<<<<
* if z > 4294967295ull: z %= p
* q *= 5ull
*/
__pyx_v_z = (__pyx_v_z * 10ULL);
102: if z > 4294967295ull: z %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":102
* if z > 1844674407370955161ull: z %= p
* z *= 10ull
* if z > 4294967295ull: z %= p # <<<<<<<<<<<<<<
* q *= 5ull
* if q > 4294967295ull: q %= p
*/
__pyx_t_1 = (__pyx_v_z > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 102; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_z = (__pyx_v_z % __pyx_v_p);
goto __pyx_L11;
}
__pyx_L11:;
103: q *= 5ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":103
* z *= 10ull
* if z > 4294967295ull: z %= p
* q *= 5ull # <<<<<<<<<<<<<<
* if q > 4294967295ull: q %= p
* if z*z%p == 1ull:
*/
__pyx_v_q = (__pyx_v_q * 5ULL);
104: if q > 4294967295ull: q %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":104
* if z > 4294967295ull: z %= p
* q *= 5ull
* if q > 4294967295ull: q %= p # <<<<<<<<<<<<<<
* if z*z%p == 1ull:
* d = non_residue(p)
*/
__pyx_t_1 = (__pyx_v_q > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 104; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_q = (__pyx_v_q % __pyx_v_p);
goto __pyx_L12;
}
__pyx_L12:;
105: if z*z%p == 1ull:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":105
* q *= 5ull
* if q > 4294967295ull: q %= p
* if z*z%p == 1ull: # <<<<<<<<<<<<<<
* d = non_residue(p)
* dp = exp_mod(d, (p-1u)>>3u, p)
*/
__pyx_t_3 = (__pyx_v_z * __pyx_v_z);
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_t_1 = ((__pyx_t_3 % __pyx_v_p) == 1ULL);
if (__pyx_t_1) {
106: d = non_residue(p)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":106
* if q > 4294967295ull: q %= p
* if z*z%p == 1ull:
* d = non_residue(p) # <<<<<<<<<<<<<<
* dp = exp_mod(d, (p-1u)>>3u, p)
* q *= dp
*/
__pyx_v_d = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_non_residue(__pyx_v_p);
107: dp = exp_mod(d, (p-1u)>>3u, p)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":107
* if z*z%p == 1ull:
* d = non_residue(p)
* dp = exp_mod(d, (p-1u)>>3u, p) # <<<<<<<<<<<<<<
* q *= dp
* if q > 4294967295ull: q %= p
*/
__pyx_v_dp = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(__pyx_v_d, ((__pyx_v_p - 1U) >> 3U), __pyx_v_p);
108: q *= dp
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":108
* d = non_residue(p)
* dp = exp_mod(d, (p-1u)>>3u, p)
* q *= dp # <<<<<<<<<<<<<<
* if q > 4294967295ull: q %= p
* dp *= dp
*/
__pyx_v_q = (__pyx_v_q * __pyx_v_dp);
109: if q > 4294967295ull: q %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":109
* dp = exp_mod(d, (p-1u)>>3u, p)
* q *= dp
* if q > 4294967295ull: q %= p # <<<<<<<<<<<<<<
* dp *= dp
* if dp > 4294967295ull: dp %= p
*/
__pyx_t_1 = (__pyx_v_q > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 109; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_q = (__pyx_v_q % __pyx_v_p);
goto __pyx_L14;
}
__pyx_L14:;
110: dp *= dp
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":110
* q *= dp
* if q > 4294967295ull: q %= p
* dp *= dp # <<<<<<<<<<<<<<
* if dp > 4294967295ull: dp %= p
* z *= dp
*/
__pyx_v_dp = (__pyx_v_dp * __pyx_v_dp);
111: if dp > 4294967295ull: dp %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":111
* if q > 4294967295ull: q %= p
* dp *= dp
* if dp > 4294967295ull: dp %= p # <<<<<<<<<<<<<<
* z *= dp
* if z > 4294967295ull: z %= p
*/
__pyx_t_1 = (__pyx_v_dp > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 111; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_dp = (__pyx_v_dp % __pyx_v_p);
goto __pyx_L15;
}
__pyx_L15:;
112: z *= dp
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":112
* dp *= dp
* if dp > 4294967295ull: dp %= p
* z *= dp # <<<<<<<<<<<<<<
* if z > 4294967295ull: z %= p
* z -= 1ull
*/
__pyx_v_z = (__pyx_v_z * __pyx_v_dp);
113: if z > 4294967295ull: z %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":113
* if dp > 4294967295ull: dp %= p
* z *= dp
* if z > 4294967295ull: z %= p # <<<<<<<<<<<<<<
* z -= 1ull
* return q*z%p
*/
__pyx_t_1 = (__pyx_v_z > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 113; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_z = (__pyx_v_z % __pyx_v_p);
goto __pyx_L16;
}
__pyx_L16:;
goto __pyx_L13;
}
__pyx_L13:;
114: z -= 1ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":114
* z *= dp
* if z > 4294967295ull: z %= p
* z -= 1ull # <<<<<<<<<<<<<<
* return q*z%p
* p -= 1u
*/
__pyx_v_z = (__pyx_v_z - 1ULL);
115: return q*z%p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":115
* if z > 4294967295ull: z %= p
* z -= 1ull
* return q*z%p # <<<<<<<<<<<<<<
* p -= 1u
* cdef uint_fast8_t r = 0u
*/
__pyx_t_3 = (__pyx_v_q * __pyx_v_z);
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 115; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_r = (__pyx_t_3 % __pyx_v_p);
goto __pyx_L0;
goto __pyx_L8;
}
__pyx_L8:;
116: p -= 1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":116 * z -= 1ull * return q*z%p * p -= 1u #<<<<<<<<<<<<<<* cdef uint_fast8_t r = 0u * q = 8ull */ __pyx_v_p = (__pyx_v_p - 1U);
117: cdef uint_fast8_t r = 0u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":117 * return q*z%p * p -= 1u * cdef uint_fast8_t r = 0u #<<<<<<<<<<<<<<* q = 8ull * while q == 8ull: */ __pyx_v_r = 0U;
118: q = 8ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":118 * p -= 1u * cdef uint_fast8_t r = 0u * q = 8ull #<<<<<<<<<<<<<<* while q == 8ull: * q = twoDiv[(p>>r)&0xFFu] */ __pyx_v_q = 8ULL;
119: while q == 8ull:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":119 * cdef uint_fast8_t r = 0u * q = 8ull * while q == 8ull: #<<<<<<<<<<<<<<* q = twoDiv[(p>>r)&0xFFu] * r += q */ while (1) { __pyx_t_1 = (__pyx_v_q == 8ULL); if (!__pyx_t_1) break;
120: q = twoDiv[(p>>r)&0xFFu]
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":120
* q = 8ull
* while q == 8ull:
* q = twoDiv[(p>>r)&0xFFu] # <<<<<<<<<<<<<<
* r += q
* q = p>>r
*/
__pyx_v_q = (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_twoDiv[((__pyx_v_p >> __pyx_v_r) & 0xFFU)]);
121: r += q
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":121
* while q == 8ull:
* q = twoDiv[(p>>r)&0xFFu]
* r += q # <<<<<<<<<<<<<<
* q = p>>r
* p += 1u
*/
__pyx_v_r = (__pyx_v_r + __pyx_v_q);
}
122: q = p>>r
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":122 * q = twoDiv[(p>>r)&0xFFu] * r += q * q = p>>r #<<<<<<<<<<<<<<* p += 1u * r -= 2u */ __pyx_v_q = (__pyx_v_p >> __pyx_v_r);
123: p += 1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":123 * r += q * q = p>>r * p += 1u #<<<<<<<<<<<<<<* r -= 2u * cdef uint_fast64_t v = exp_mod(non_residue(p), q, p) */ __pyx_v_p = (__pyx_v_p + 1U);
124: r -= 2u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":124 * q = p>>r * p += 1u * r -= 2u #<<<<<<<<<<<<<<* cdef uint_fast64_t v = exp_mod(non_residue(p), q, p) * d = exp_mod(5ull, (q-1u)>>1u, p) */ __pyx_v_r = (__pyx_v_r - 2U);
125: cdef uint_fast64_t v = exp_mod(non_residue(p), q, p)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":125 * p += 1u * r -= 2u * cdef uint_fast64_t v = exp_mod(non_residue(p), q, p) #<<<<<<<<<<<<<<* d = exp_mod(5ull, (q-1u)>>1u, p) * cdef uint_fast64_t res = 5ull*d */ __pyx_v_v = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(__pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_non_residue(__pyx_v_p), __pyx_v_q, __pyx_v_p);
126: d = exp_mod(5ull, (q-1u)>>1u, p)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":126 * r -= 2u * cdef uint_fast64_t v = exp_mod(non_residue(p), q, p) * d = exp_mod(5ull, (q-1u)>>1u, p) #<<<<<<<<<<<<<<* cdef uint_fast64_t res = 5ull*d * if res > 4294967295ull: res %= p */ __pyx_v_d = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(5ULL, ((__pyx_v_q - 1U) >> 1U), __pyx_v_p);
127: cdef uint_fast64_t res = 5ull*d
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":127 * cdef uint_fast64_t v = exp_mod(non_residue(p), q, p) * d = exp_mod(5ull, (q-1u)>>1u, p) * cdef uint_fast64_t res = 5ull*d #<<<<<<<<<<<<<<* if res > 4294967295ull: res %= p * d *= d */ __pyx_v_res = (5ULL * __pyx_v_d);
128: if res > 4294967295ull: res %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":128 * d = exp_mod(5ull, (q-1u)>>1u, p) * cdef uint_fast64_t res = 5ull*d * if res > 4294967295ull: res %= p #<<<<<<<<<<<<<<* d *= d * if d > 3689348814741910323ull: d %= p */ __pyx_t_1 = (__pyx_v_res > 4294967295ULL); if (__pyx_t_1) { if (unlikely(__pyx_v_p == 0)) { PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero"); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 128; __pyx_clineno = __LINE__; goto __pyx_L1_error;} } __pyx_v_res = (__pyx_v_res % __pyx_v_p); goto __pyx_L19; } __pyx_L19:;
129: d *= d
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":129 * cdef uint_fast64_t res = 5ull*d * if res > 4294967295ull: res %= p * d *= d #<<<<<<<<<<<<<<* if d > 3689348814741910323ull: d %= p * d *= 5ull */ __pyx_v_d = (__pyx_v_d * __pyx_v_d);
130: if d > 3689348814741910323ull: d %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":130 * if res > 4294967295ull: res %= p * d *= d * if d > 3689348814741910323ull: d %= p #<<<<<<<<<<<<<<* d *= 5ull * d %= p */ __pyx_t_1 = (__pyx_v_d > 3689348814741910323ULL); if (__pyx_t_1) { if (unlikely(__pyx_v_p == 0)) { PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero"); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 130; __pyx_clineno = __LINE__; goto __pyx_L1_error;} } __pyx_v_d = (__pyx_v_d % __pyx_v_p); goto __pyx_L20; } __pyx_L20:;
131: d *= 5ull
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":131 * d *= d * if d > 3689348814741910323ull: d %= p * d *= 5ull #<<<<<<<<<<<<<<* d %= p * cdef uint_fast8_t m */ __pyx_v_d = (__pyx_v_d * 5ULL);
132: d %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":132 * if d > 3689348814741910323ull: d %= p * d *= 5ull * d %= p #<<<<<<<<<<<<<<* cdef uint_fast8_t m * while not d == 1u: */ if (unlikely(__pyx_v_p == 0)) { PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero"); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 132; __pyx_clineno = __LINE__; goto __pyx_L1_error;} } __pyx_v_d = (__pyx_v_d % __pyx_v_p);
133: cdef uint_fast8_t m
134: while not d == 1u:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":134 * d %= p * cdef uint_fast8_t m * while not d == 1u: #<<<<<<<<<<<<<<* m = r * dp = d*d%p */ while (1) { __pyx_t_1 = (!(__pyx_v_d == 1U)); if (!__pyx_t_1) break;
135: m = r
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":135
* cdef uint_fast8_t m
* while not d == 1u:
* m = r # <<<<<<<<<<<<<<
* dp = d*d%p
* while not dp == 1u:
*/
__pyx_v_m = __pyx_v_r;
136: dp = d*d%p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":136
* while not d == 1u:
* m = r
* dp = d*d%p # <<<<<<<<<<<<<<
* while not dp == 1u:
* dp *= dp
*/
__pyx_t_2 = (__pyx_v_d * __pyx_v_d);
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 136; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_dp = (__pyx_t_2 % __pyx_v_p);
137: while not dp == 1u:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":137
* m = r
* dp = d*d%p
* while not dp == 1u: # <<<<<<<<<<<<<<
* dp *= dp
* dp %= p
*/
while (1) {
__pyx_t_1 = (!(__pyx_v_dp == 1U));
if (!__pyx_t_1) break;
138: dp *= dp
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":138
* dp = d*d%p
* while not dp == 1u:
* dp *= dp # <<<<<<<<<<<<<<
* dp %= p
* m -= 1u
*/
__pyx_v_dp = (__pyx_v_dp * __pyx_v_dp);
139: dp %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":139
* while not dp == 1u:
* dp *= dp
* dp %= p # <<<<<<<<<<<<<<
* m -= 1u
* z = exp_mod(v, shiftTab[m], p)
*/
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 139; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_dp = (__pyx_v_dp % __pyx_v_p);
140: m -= 1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":140
* dp *= dp
* dp %= p
* m -= 1u # <<<<<<<<<<<<<<
* z = exp_mod(v, shiftTab[m], p)
* res *= z
*/
__pyx_v_m = (__pyx_v_m - 1U);
}
141: z = exp_mod(v, shiftTab[m], p)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":141
* dp %= p
* m -= 1u
* z = exp_mod(v, shiftTab[m], p) # <<<<<<<<<<<<<<
* res *= z
* if res > 4294967295ull: res %= p
*/
__pyx_v_z = __pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_exp_mod(__pyx_v_v, (__pyx_v_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_shiftTab[__pyx_v_m]), __pyx_v_p);
142: res *= z
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":142
* m -= 1u
* z = exp_mod(v, shiftTab[m], p)
* res *= z # <<<<<<<<<<<<<<
* if res > 4294967295ull: res %= p
* z *= z
*/
__pyx_v_res = (__pyx_v_res * __pyx_v_z);
143: if res > 4294967295ull: res %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":143
* z = exp_mod(v, shiftTab[m], p)
* res *= z
* if res > 4294967295ull: res %= p # <<<<<<<<<<<<<<
* z *= z
* if z > 4294967295ull: z %= p
*/
__pyx_t_1 = (__pyx_v_res > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 143; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_res = (__pyx_v_res % __pyx_v_p);
goto __pyx_L25;
}
__pyx_L25:;
144: z *= z
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":144
* res *= z
* if res > 4294967295ull: res %= p
* z *= z # <<<<<<<<<<<<<<
* if z > 4294967295ull: z %= p
* d *= z
*/
__pyx_v_z = (__pyx_v_z * __pyx_v_z);
145: if z > 4294967295ull: z %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":145
* if res > 4294967295ull: res %= p
* z *= z
* if z > 4294967295ull: z %= p # <<<<<<<<<<<<<<
* d *= z
* d %= p
*/
__pyx_t_1 = (__pyx_v_z > 4294967295ULL);
if (__pyx_t_1) {
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 145; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_z = (__pyx_v_z % __pyx_v_p);
goto __pyx_L26;
}
__pyx_L26:;
146: d *= z
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":146
* z *= z
* if z > 4294967295ull: z %= p
* d *= z # <<<<<<<<<<<<<<
* d %= p
* return res%p
*/
__pyx_v_d = (__pyx_v_d * __pyx_v_z);
147: d %= p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":147
* if z > 4294967295ull: z %= p
* d *= z
* d %= p # <<<<<<<<<<<<<<
* return res%p
*
*/
if (unlikely(__pyx_v_p == 0)) {
PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero");
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 147; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_d = (__pyx_v_d % __pyx_v_p);
}
148: return res%p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":148 * d *= z * d %= p * return res%p #<<<<<<<<<<<<<<* * def get_primes(p): */ if (unlikely(__pyx_v_p == 0)) { PyErr_Format(PyExc_ZeroDivisionError, "integer division or modulo by zero"); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 148; __pyx_clineno = __LINE__; goto __pyx_L1_error;} } __pyx_r = (__pyx_v_res % __pyx_v_p); goto __pyx_L0; __pyx_r = 0; goto __pyx_L0; __pyx_L1_error:; __Pyx_WriteUnraisable("_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.sqrt5_mod"); __pyx_r = 0; __pyx_L0:; __Pyx_RefNannyFinishContext(); return __pyx_r; }
149:
150: def get_primes(p):
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":150 * return res%p * * def get_primes(p): #<<<<<<<<<<<<<<* q = sqrt5_mod(p)-1u * w = ((p+1u)>>1u)*q%p */ static PyObject *__pyx_pf_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_get_primes(PyObject *__pyx_self, PyObject *__pyx_v_p); /*proto*/ static char __pyx_doc_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_get_primes[] = "File: _home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx (starting at line 150)"; static PyMethodDef __pyx_mdef_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_get_primes = {__Pyx_NAMESTR("get_primes"), (PyCFunction)__pyx_pf_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_get_primes, METH_O, __Pyx_DOCSTR(__pyx_doc_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_get_primes)}; static PyObject *__pyx_pf_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_get_primes(PyObject *__pyx_self, PyObject *__pyx_v_p) { PyObject *__pyx_v_q; PyObject *__pyx_v_w; PyObject *__pyx_r = NULL; __Pyx_RefNannySetupContext("get_primes"); __pyx_self = __pyx_self; __pyx_v_q = Py_None; __Pyx_INCREF(Py_None); __pyx_v_w = Py_None; __Pyx_INCREF(Py_None); /* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":150 * return res%p * * def get_primes(p): #<<<<<<<<<<<<<<* q = sqrt5_mod(p)-1u * w = ((p+1u)>>1u)*q%p */ __pyx_t_2 = PyCFunction_NewEx(&__pyx_mdef_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_get_primes, NULL, __pyx_n_s_3); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 150; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_2); if (PyObject_SetAttr(__pyx_m, __pyx_n_s__get_primes, __pyx_t_2)<0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 150; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
151: q = sqrt5_mod(p)-1u
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":151 * * def get_primes(p): * q = sqrt5_mod(p)-1u #<<<<<<<<<<<<<<* w = ((p+1u)>>1u)*q%p * q = p-1u-w */ __pyx_t_1 = __Pyx_PyInt_from_py_uint_fast32_t(__pyx_v_p); if (unlikely((__pyx_t_1 == (uint_fast32_t)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 151; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __pyx_t_2 = PyLong_FromUnsignedLong((__pyx_f_73_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0_sqrt5_mod(__pyx_t_1) - 1U)); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 151; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_2); __Pyx_DECREF(__pyx_v_q); __pyx_v_q = __pyx_t_2; __pyx_t_2 = 0;
152: w = ((p+1u)>>1u)*q%p
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":152 * def get_primes(p): * q = sqrt5_mod(p)-1u * w = ((p+1u)>>1u)*q%p #<<<<<<<<<<<<<<* q = p-1u-w * if w<q: */ __pyx_t_2 = PyNumber_Add(__pyx_v_p, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 152; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_2); __pyx_t_3 = PyNumber_Rshift(__pyx_t_2, __pyx_int_1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 152; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_3); __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; __pyx_t_2 = PyNumber_Multiply(__pyx_t_3, __pyx_v_q); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 152; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_2); __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; __pyx_t_3 = PyNumber_Remainder(__pyx_t_2, __pyx_v_p); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 152; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_3); __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; __Pyx_DECREF(__pyx_v_w); __pyx_v_w = __pyx_t_3; __pyx_t_3 = 0;
153: q = p-1u-w
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":153 * q = sqrt5_mod(p)-1u * w = ((p+1u)>>1u)*q%p * q = p-1u-w #<<<<<<<<<<<<<<* if w<q: * return (w,q) */ __pyx_t_3 = PyNumber_Subtract(__pyx_v_p, __pyx_int_1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 153; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_3); __pyx_t_2 = PyNumber_Subtract(__pyx_t_3, __pyx_v_w); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 153; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_2); __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; __Pyx_DECREF(__pyx_v_q); __pyx_v_q = __pyx_t_2; __pyx_t_2 = 0;
154: if w < q:
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":154 * w = ((p+1u)>>1u)*q%p * q = p-1u-w * if w<q: #<<<<<<<<<<<<<<* return (w,q) * return (q,w) */ __pyx_t_2 = PyObject_RichCompare(__pyx_v_w, __pyx_v_q, Py_LT); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 154; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(__pyx_t_2); __pyx_t_4 = __Pyx_PyObject_IsTrue(__pyx_t_2); if (unlikely(__pyx_t_4<0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 154; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; if (__pyx_t_4) {
155: return (w,q)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":155
* q = p-1u-w
* if w < q:
* return (w,q) # <<<<<<<<<<<<<<
* return (q,w)
*/
__Pyx_XDECREF(__pyx_r);
__pyx_t_2 = PyTuple_New(2); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 155; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
__Pyx_GOTREF(((PyObject *)__pyx_t_2));
__Pyx_INCREF(__pyx_v_w);
PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_w);
__Pyx_GIVEREF(__pyx_v_w);
__Pyx_INCREF(__pyx_v_q);
PyTuple_SET_ITEM(__pyx_t_2, 1, __pyx_v_q);
__Pyx_GIVEREF(__pyx_v_q);
__pyx_r = ((PyObject *)__pyx_t_2);
__pyx_t_2 = 0;
goto __pyx_L0;
goto __pyx_L5;
}
__pyx_L5:;
156: return (q,w)
/* "_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.pyx":156 * if w<q: * return (w,q) * return (q,w) #<<<<<<<<<<<<<<*/ __Pyx_XDECREF(__pyx_r); __pyx_t_2 = PyTuple_New(2); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 156; __pyx_clineno = __LINE__; goto __pyx_L1_error;} __Pyx_GOTREF(((PyObject *)__pyx_t_2)); __Pyx_INCREF(__pyx_v_q); PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_q); __Pyx_GIVEREF(__pyx_v_q); __Pyx_INCREF(__pyx_v_w); PyTuple_SET_ITEM(__pyx_t_2, 1, __pyx_v_w); __Pyx_GIVEREF(__pyx_v_w); __pyx_r = ((PyObject *)__pyx_t_2); __pyx_t_2 = 0; goto __pyx_L0; __pyx_r = Py_None; __Pyx_INCREF(Py_None); goto __pyx_L0; __pyx_L1_error:; __Pyx_XDECREF(__pyx_t_2); __Pyx_XDECREF(__pyx_t_3); __Pyx_AddTraceback("_home_psharaba__sage_sage_notebook_sagenb_home_admin_19_code_sage3_spyx_0.get_primes"); __pyx_r = NULL; __pyx_L0:; __Pyx_DECREF(__pyx_v_q); __Pyx_DECREF(__pyx_v_w); __Pyx_XGIVEREF(__pyx_r); __Pyx_RefNannyFinishContext(); return __pyx_r; }