Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

#***************************************************************************** 

# Copyright (C) 2005 William Stein <wstein@gmail.com> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# 

# This code is distributed in the hope that it will be useful, 

# but WITHOUT ANY WARRANTY; without even the implied warranty of 

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 

# General Public License for more details. 

# 

# The full text of the GPL is available at: 

# 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

  

from __future__ import absolute_import, print_function 

  

from cysignals.signals cimport sig_on, sig_off 

from sage.ext.cplusplus cimport ccrepr, ccreadstr 

  

include 'misc.pxi' 

include 'decl.pxi' 

  

from cpython.object cimport Py_EQ, Py_NE 

  

from sage.rings.integer import Integer 

from sage.rings.integer_ring import IntegerRing 

from sage.rings.integer cimport Integer 

from sage.libs.ntl.ntl_ZZ cimport ntl_ZZ 

from sage.libs.ntl.ntl_ZZ_p cimport ntl_ZZ_p 

from sage.rings.integer cimport Integer 

from sage.rings.integer_ring cimport IntegerRing_class 

  

from sage.libs.ntl.convert cimport PyLong_to_ZZ 

from sage.libs.ntl.ntl_ZZ import unpickle_class_args 

  

from sage.libs.ntl.ntl_ZZ_pContext cimport ntl_ZZ_pContext_class 

from sage.libs.ntl.ntl_ZZ_pContext import ntl_ZZ_pContext 

  

from sage.libs.ntl.ntl_ZZ_pEContext cimport ntl_ZZ_pEContext_class 

from sage.libs.ntl.ntl_ZZ_pEContext import ntl_ZZ_pEContext 

  

  

ZZ_sage = IntegerRing() 

  

  

############################################################################## 

# 

# ZZ_pE_c: An extension of the integers modulo p 

# 

############################################################################## 

cdef class ntl_ZZ_pE(object): 

r""" 

The \class{ZZ_pE} class is used to model $\Z / p\Z [x] / (f(x))$. 

The modulus $p$ may be any positive integer, not necessarily prime, 

and the modulus f is not required to be irreducible. 

  

Objects of the class \class{ZZ_pE} are represented as a \code{ZZ_pX} of 

degree less than the degree of $f$. 

  

Each \class{ZZ_pE} contains a pointer of a \class{ZZ_pEContext} which 

contains pre-computed data for NTL. These can be explicitly constructed 

and passed to the constructor of a \class{ZZ_pE} or the \class{ZZ_pEContext} 

method \code{ZZ_pE} can be used to construct a \class{ZZ_pE} element. 

  

This class takes care of making sure that the C++ library NTL global 

variable is set correctly before performing any arithmetic. 

""" 

def __init__(self, v=None, modulus=None): 

r""" 

Initializes an ntl ZZ_pE. 

  

EXAMPLES: 

sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) 

sage: c.ZZ_pE([13,4,1]) 

[1 3] 

sage: c.ZZ_pE(Integer(95413094)) 

[7] 

sage: c.ZZ_pE(long(223895239852389582988)) 

[5] 

sage: c.ZZ_pE('[1]') 

[1] 

  

AUTHOR: David Roe (2007-9-25) 

""" 

if isinstance(modulus, ntl_ZZ_pEContext_class): 

self.c = <ntl_ZZ_pEContext_class>modulus 

elif isinstance(modulus, ntl_ZZ_pX): 

modulus.get_modulus_context().restore() 

self.c = <ntl_ZZ_pEContext_class>ntl_ZZ_pEContext(<ntl_ZZ_pX>modulus) 

elif isinstance(v, ntl_ZZ_pE): 

self.c = (<ntl_ZZ_pE>v).c 

elif isinstance(v, tuple) and len(v) == 2 and isinstance(v[1], ntl_ZZ_pEContext_class): 

self.c = v[1] 

v = v[0] 

else: 

raise ValueError("You must specify a modulus when creating a ZZ_pE.") 

self.c.restore_c() 

  

cdef ZZ_c temp 

cdef ntl_ZZ_pX tmp_zzpx 

if v is not None: 

if isinstance(v, ntl_ZZ_pE): 

if (<ntl_ZZ_pE>v).c is not self.c: 

raise ValueError("You cannot cast between rings with different moduli") 

self.x = (<ntl_ZZ_pE>v).x 

elif isinstance(v, ntl_ZZ_pX): 

if (<ntl_ZZ_pX>v).c is not self.c.pc: 

raise ValueError("You cannot cast between rings with different moduli") 

self.x = ZZ_pX_to_ZZ_pE((<ntl_ZZ_pX>v).x) 

elif isinstance(v, list) or isinstance(v, tuple): 

tmp_zzpx = <ntl_ZZ_pX>ntl_ZZ_pX(v, self.c.pc) 

# random values without the following restore call 

# surely because the above call restore things and breaks the modulus 

self.c.restore_c() 

self.x = ZZ_pX_to_ZZ_pE(tmp_zzpx.x) 

elif isinstance(v, long): 

PyLong_to_ZZ(&temp, v) 

self.x = ZZ_to_ZZ_pE(temp) 

elif isinstance(v, int): 

self.x = long_to_ZZ_pE(v) 

elif isinstance(v, ntl_ZZ_p): 

self.x = ZZ_p_to_ZZ_pE((<ntl_ZZ_p>v).x) 

elif isinstance(v, ntl_ZZ): 

self.x = ZZ_to_ZZ_pE((<ntl_ZZ>v).x) 

elif isinstance(v, Integer): 

(<Integer>v)._to_ZZ(&temp) 

self.x = ZZ_to_ZZ_pE(temp) 

else: 

ccreadstr(self.x, str(v)) 

  

def __cinit__(ntl_ZZ_pE self, v=None, modulus=None): 

#################### WARNING ################### 

## Before creating a ZZ_pE, you must create a ## 

## ZZ_pEContext, and restore it. In Python, ## 

## the error checking in __init__ will prevent## 

## you from constructing an ntl_ZZ_pE ## 

## inappropriately. However, from Cython, you## 

## could do r = ntl_ZZ_pE.__new__(ntl_ZZ_pE) without 

## first restoring a ZZ_pEContext, which could## 

## have unfortunate consequences. See _new ## 

## defined below for an example of the right ## 

## way to short-circuit __init__ (or just call## 

## _new in your own code). ## 

################################################ 

if modulus is None: 

return 

if isinstance(modulus, ntl_ZZ_pEContext_class): 

self.c = <ntl_ZZ_pEContext_class>modulus 

self.c.restore_c() 

else: 

self.c = <ntl_ZZ_pEContext_class>ntl_ZZ_pEContext(modulus) 

self.c.restore_c() 

  

cdef ntl_ZZ_pE _new(self): 

cdef ntl_ZZ_pE r 

self.c.restore_c() 

r = ntl_ZZ_pE.__new__(ntl_ZZ_pE) 

r.c = self.c 

return r 

  

def __reduce__(self): 

""" 

sage: a = ntl.ZZ_pE([4],ntl.ZZ_pX([1,1,1],ntl.ZZ(7))) 

sage: loads(dumps(a)) == a 

True 

""" 

return make_ZZ_pE, (self.get_as_ZZ_pX(), self.get_modulus_context()) 

  

def get_modulus_context(self): 

return self.c 

  

def __repr__(self): 

self.c.restore_c() 

return ccrepr(self.x) 

  

def __richcmp__(ntl_ZZ_pE self, other, int op): 

r""" 

Compare self to other. 

  

EXAMPLES:: 

  

sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) 

sage: c.ZZ_pE([13,1,1])==c.ZZ_pE(1) 

True 

sage: c.ZZ_pE(35r)==c.ZZ_pE(1) 

False 

sage: c.ZZ_pE(35r) == 2 

True 

""" 

self.c.restore_c() 

  

if op != Py_EQ and op != Py_NE: 

raise TypeError("integers mod p are not ordered") 

  

cdef ntl_ZZ_pE b 

try: 

b = <ntl_ZZ_pE?>other 

except TypeError: 

b = ntl_ZZ_pE(other, self.c) 

  

return (op == Py_EQ) == (self.x == b.x) 

  

def __invert__(ntl_ZZ_pE self): 

r""" 

EXAMPLES: 

sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([2,7,1],11)) 

sage: ~ntl.ZZ_pE([1,1],modulus=c) 

[7 3] 

""" 

cdef ntl_ZZ_pE r = self._new() 

sig_on() 

self.c.restore_c() 

ZZ_pE_inv(r.x, self.x) 

sig_off() 

return r 

  

def __mul__(ntl_ZZ_pE self, other): 

cdef ntl_ZZ_pE y 

cdef ntl_ZZ_pE r = self._new() 

if not isinstance(other, ntl_ZZ_pE): 

other = ntl_ZZ_pE(other,self.c) 

elif self.c is not (<ntl_ZZ_pE>other).c: 

raise ValueError("You can not perform arithmetic with elements of different moduli.") 

y = other 

self.c.restore_c() 

ZZ_pE_mul(r.x, self.x, y.x) 

return r 

  

def __sub__(ntl_ZZ_pE self, other): 

if not isinstance(other, ntl_ZZ_pE): 

other = ntl_ZZ_pE(other,self.c) 

elif self.c is not (<ntl_ZZ_pE>other).c: 

raise ValueError("You can not perform arithmetic with elements of different moduli.") 

cdef ntl_ZZ_pE r = self._new() 

self.c.restore_c() 

ZZ_pE_sub(r.x, self.x, (<ntl_ZZ_pE>other).x) 

return r 

  

def __add__(ntl_ZZ_pE self, other): 

cdef ntl_ZZ_pE y 

cdef ntl_ZZ_pE r = self._new() 

if not isinstance(other, ntl_ZZ_pE): 

other = ntl_ZZ_pE(other,modulus=self.c) 

elif self.c is not (<ntl_ZZ_pE>other).c: 

raise ValueError("You can not perform arithmetic with elements of different moduli.") 

y = other 

sig_on() 

self.c.restore_c() 

ZZ_pE_add(r.x, self.x, y.x) 

sig_off() 

return r 

  

def __neg__(ntl_ZZ_pE self): 

cdef ntl_ZZ_pE r = self._new() 

sig_on() 

self.c.restore_c() 

ZZ_pE_negate(r.x, self.x) 

sig_off() 

return r 

  

def __pow__(ntl_ZZ_pE self, long e, ignored): 

cdef ntl_ZZ_pE r = self._new() 

sig_on() 

self.c.restore_c() 

ZZ_pE_power(r.x, self.x, e) 

sig_off() 

return r 

  

  

cdef ntl_ZZ_pX get_as_ZZ_pX(ntl_ZZ_pE self): 

r""" 

Returns value as ntl_ZZ_pX. 

""" 

self.c.restore_c() 

cdef ntl_ZZ_pX y = ntl_ZZ_pX.__new__(ntl_ZZ_pX) 

y.c = self.c.pc 

sig_on() 

y.x = ZZ_pE_to_ZZ_pX(self.x) 

sig_off() 

return y 

  

def get_as_ZZ_pX_doctest(self): 

r""" 

This method exists solely for automated testing of get_as_ZZ_pX(). 

  

sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) 

sage: x = ntl.ZZ_pE([42,1],modulus=c) 

sage: i = x.get_as_ZZ_pX_doctest() 

sage: i 

[9 1] 

sage: type(i) 

<type 'sage.libs.ntl.ntl_ZZ_pX.ntl_ZZ_pX'> 

""" 

return self.get_as_ZZ_pX() 

  

cdef void set_from_ZZ_pX(ntl_ZZ_pE self, ntl_ZZ_pX value): 

r""" 

Sets the value from a ZZ_pX. 

""" 

self.c.restore_c() 

self.x = ZZ_pX_to_ZZ_pE(value.x) 

  

def set_from_ZZ_pX_doctest(self, value): 

r""" 

This method exists solely for automated testing of set_from_ZZ_pX(). 

  

sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) 

sage: x = ntl.ZZ_pE(modulus=c) 

sage: x.set_from_ZZ_pX_doctest(ntl.ZZ_pX([5,2,1],11)) 

sage: x 

[4 1] 

""" 

self.set_from_ZZ_pX(value) 

  

#def lift(self): 

# cdef ntl_ZZ r = ntl_ZZ() 

# self.c.restore_c() 

# r.x = rep(self.x) 

# return r 

  

def modulus(self): 

r""" 

Returns the modulus as an NTL ZZ_pX. 

  

sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) 

sage: n=ntl.ZZ_pE([2983,233],c) 

sage: n.modulus() 

[1 1 1] 

""" 

self.c.restore_c() 

cdef ntl_ZZ_pX r = ntl_ZZ_pX(v = None, modulus=self.c.pc) 

r.x = (<ntl_ZZ_pX>self.c.f).x 

return r 

  

def make_ZZ_pE(x, c): 

""" 

Here for unpickling. 

  

EXAMPLES: 

sage: c = ntl.ZZ_pEContext(ntl.ZZ_pX([-5,0,1],25)) 

sage: sage.libs.ntl.ntl_ZZ_pE.make_ZZ_pE([4,3], c) 

[4 3] 

sage: type(sage.libs.ntl.ntl_ZZ_pE.make_ZZ_pE([4,3], c)) 

<type 'sage.libs.ntl.ntl_ZZ_pE.ntl_ZZ_pE'> 

""" 

return ntl_ZZ_pE(x, c)