KaneAI - World’s First E2E Software Testing Agent.Book a Demo 
How to use red method in green
Best Python code snippet using green
short.js
Source:short.js 
1/* */ 2'use strict';3var curve = require('./index');4var elliptic = require('../../elliptic');5var BN = require('bn.js');6var inherits = require('inherits');7var Base = curve.base;8var assert = elliptic.utils.assert;9function ShortCurve(conf) {10 Base.call(this, 'short', conf);11 this.a = new BN(conf.a, 16).toRed(this.red);12 this.b = new BN(conf.b, 16).toRed(this.red);13 this.tinv = this.two.redInvm();14 this.zeroA = this.a.fromRed().cmpn(0) === 0;15 this.threeA = this.a.fromRed().sub(this.p).cmpn(-3) === 0;16 this.endo = this._getEndomorphism(conf);17 this._endoWnafT1 = new Array(4);18 this._endoWnafT2 = new Array(4);19}20inherits(ShortCurve, Base);21module.exports = ShortCurve;22ShortCurve.prototype._getEndomorphism = function _getEndomorphism(conf) {23 if (!this.zeroA || !this.g || !this.n || this.p.modn(3) !== 1)24 return;25 var beta;26 var lambda;27 if (conf.beta) {28 beta = new BN(conf.beta, 16).toRed(this.red);29 } else {30 var betas = this._getEndoRoots(this.p);31 beta = betas[0].cmp(betas[1]) < 0 ? betas[0] : betas[1];32 beta = beta.toRed(this.red);33 }34 if (conf.lambda) {35 lambda = new BN(conf.lambda, 16);36 } else {37 var lambdas = this._getEndoRoots(this.n);38 if (this.g.mul(lambdas[0]).x.cmp(this.g.x.redMul(beta)) === 0) {39 lambda = lambdas[0];40 } else {41 lambda = lambdas[1];42 assert(this.g.mul(lambda).x.cmp(this.g.x.redMul(beta)) === 0);43 }44 }45 var basis;46 if (conf.basis) {47 basis = conf.basis.map(function(vec) {48 return {49 a: new BN(vec.a, 16),50 b: new BN(vec.b, 16)51 };52 });53 } else {54 basis = this._getEndoBasis(lambda);55 }56 return {57 beta: beta,58 lambda: lambda,59 basis: basis60 };61};62ShortCurve.prototype._getEndoRoots = function _getEndoRoots(num) {63 var red = num === this.p ? this.red : BN.mont(num);64 var tinv = new BN(2).toRed(red).redInvm();65 var ntinv = tinv.redNeg();66 var s = new BN(3).toRed(red).redNeg().redSqrt().redMul(tinv);67 var l1 = ntinv.redAdd(s).fromRed();68 var l2 = ntinv.redSub(s).fromRed();69 return [l1, l2];70};71ShortCurve.prototype._getEndoBasis = function _getEndoBasis(lambda) {72 var aprxSqrt = this.n.ushrn(Math.floor(this.n.bitLength() / 2));73 var u = lambda;74 var v = this.n.clone();75 var x1 = new BN(1);76 var y1 = new BN(0);77 var x2 = new BN(0);78 var y2 = new BN(1);79 var a0;80 var b0;81 var a1;82 var b1;83 var a2;84 var b2;85 var prevR;86 var i = 0;87 var r;88 var x;89 while (u.cmpn(0) !== 0) {90 var q = v.div(u);91 r = v.sub(q.mul(u));92 x = x2.sub(q.mul(x1));93 var y = y2.sub(q.mul(y1));94 if (!a1 && r.cmp(aprxSqrt) < 0) {95 a0 = prevR.neg();96 b0 = x1;97 a1 = r.neg();98 b1 = x;99 } else if (a1 && ++i === 2) {100 break;101 }102 prevR = r;103 v = u;104 u = r;105 x2 = x1;106 x1 = x;107 y2 = y1;108 y1 = y;109 }110 a2 = r.neg();111 b2 = x;112 var len1 = a1.sqr().add(b1.sqr());113 var len2 = a2.sqr().add(b2.sqr());114 if (len2.cmp(len1) >= 0) {115 a2 = a0;116 b2 = b0;117 }118 if (a1.negative) {119 a1 = a1.neg();120 b1 = b1.neg();121 }122 if (a2.negative) {123 a2 = a2.neg();124 b2 = b2.neg();125 }126 return [{127 a: a1,128 b: b1129 }, {130 a: a2,131 b: b2132 }];133};134ShortCurve.prototype._endoSplit = function _endoSplit(k) {135 var basis = this.endo.basis;136 var v1 = basis[0];137 var v2 = basis[1];138 var c1 = v2.b.mul(k).divRound(this.n);139 var c2 = v1.b.neg().mul(k).divRound(this.n);140 var p1 = c1.mul(v1.a);141 var p2 = c2.mul(v2.a);142 var q1 = c1.mul(v1.b);143 var q2 = c2.mul(v2.b);144 var k1 = k.sub(p1).sub(p2);145 var k2 = q1.add(q2).neg();146 return {147 k1: k1,148 k2: k2149 };150};151ShortCurve.prototype.pointFromX = function pointFromX(x, odd) {152 x = new BN(x, 16);153 if (!x.red)154 x = x.toRed(this.red);155 var y2 = x.redSqr().redMul(x).redIAdd(x.redMul(this.a)).redIAdd(this.b);156 var y = y2.redSqrt();157 if (y.redSqr().redSub(y2).cmp(this.zero) !== 0)158 throw new Error('invalid point');159 var isOdd = y.fromRed().isOdd();160 if (odd && !isOdd || !odd && isOdd)161 y = y.redNeg();162 return this.point(x, y);163};164ShortCurve.prototype.validate = function validate(point) {165 if (point.inf)166 return true;167 var x = point.x;168 var y = point.y;169 var ax = this.a.redMul(x);170 var rhs = x.redSqr().redMul(x).redIAdd(ax).redIAdd(this.b);171 return y.redSqr().redISub(rhs).cmpn(0) === 0;172};173ShortCurve.prototype._endoWnafMulAdd = function _endoWnafMulAdd(points, coeffs) {174 var npoints = this._endoWnafT1;175 var ncoeffs = this._endoWnafT2;176 for (var i = 0; i < points.length; i++) {177 var split = this._endoSplit(coeffs[i]);178 var p = points[i];179 var beta = p._getBeta();180 if (split.k1.negative) {181 split.k1.ineg();182 p = p.neg(true);183 }184 if (split.k2.negative) {185 split.k2.ineg();186 beta = beta.neg(true);187 }188 npoints[i * 2] = p;189 npoints[i * 2 + 1] = beta;190 ncoeffs[i * 2] = split.k1;191 ncoeffs[i * 2 + 1] = split.k2;192 }193 var res = this._wnafMulAdd(1, npoints, ncoeffs, i * 2);194 for (var j = 0; j < i * 2; j++) {195 npoints[j] = null;196 ncoeffs[j] = null;197 }198 return res;199};200function Point(curve, x, y, isRed) {201 Base.BasePoint.call(this, curve, 'affine');202 if (x === null && y === null) {203 this.x = null;204 this.y = null;205 this.inf = true;206 } else {207 this.x = new BN(x, 16);208 this.y = new BN(y, 16);209 if (isRed) {210 this.x.forceRed(this.curve.red);211 this.y.forceRed(this.curve.red);212 }213 if (!this.x.red)214 this.x = this.x.toRed(this.curve.red);215 if (!this.y.red)216 this.y = this.y.toRed(this.curve.red);217 this.inf = false;218 }219}220inherits(Point, Base.BasePoint);221ShortCurve.prototype.point = function point(x, y, isRed) {222 return new Point(this, x, y, isRed);223};224ShortCurve.prototype.pointFromJSON = function pointFromJSON(obj, red) {225 return Point.fromJSON(this, obj, red);226};227Point.prototype._getBeta = function _getBeta() {228 if (!this.curve.endo)229 return;230 var pre = this.precomputed;231 if (pre && pre.beta)232 return pre.beta;233 var beta = this.curve.point(this.x.redMul(this.curve.endo.beta), this.y);234 if (pre) {235 var curve = this.curve;236 var endoMul = function(p) {237 return curve.point(p.x.redMul(curve.endo.beta), p.y);238 };239 pre.beta = beta;240 beta.precomputed = {241 beta: null,242 naf: pre.naf && {243 wnd: pre.naf.wnd,244 points: pre.naf.points.map(endoMul)245 },246 doubles: pre.doubles && {247 step: pre.doubles.step,248 points: pre.doubles.points.map(endoMul)249 }250 };251 }252 return beta;253};254Point.prototype.toJSON = function toJSON() {255 if (!this.precomputed)256 return [this.x, this.y];257 return [this.x, this.y, this.precomputed && {258 doubles: this.precomputed.doubles && {259 step: this.precomputed.doubles.step,260 points: this.precomputed.doubles.points.slice(1)261 },262 naf: this.precomputed.naf && {263 wnd: this.precomputed.naf.wnd,264 points: this.precomputed.naf.points.slice(1)265 }266 }];267};268Point.fromJSON = function fromJSON(curve, obj, red) {269 if (typeof obj === 'string')270 obj = JSON.parse(obj);271 var res = curve.point(obj[0], obj[1], red);272 if (!obj[2])273 return res;274 function obj2point(obj) {275 return curve.point(obj[0], obj[1], red);276 }277 var pre = obj[2];278 res.precomputed = {279 beta: null,280 doubles: pre.doubles && {281 step: pre.doubles.step,282 points: [res].concat(pre.doubles.points.map(obj2point))283 },284 naf: pre.naf && {285 wnd: pre.naf.wnd,286 points: [res].concat(pre.naf.points.map(obj2point))287 }288 };289 return res;290};291Point.prototype.inspect = function inspect() {292 if (this.isInfinity())293 return '<EC Point Infinity>';294 return '<EC Point x: ' + this.x.fromRed().toString(16, 2) + ' y: ' + this.y.fromRed().toString(16, 2) + '>';295};296Point.prototype.isInfinity = function isInfinity() {297 return this.inf;298};299Point.prototype.add = function add(p) {300 if (this.inf)301 return p;302 if (p.inf)303 return this;304 if (this.eq(p))305 return this.dbl();306 if (this.neg().eq(p))307 return this.curve.point(null, null);308 if (this.x.cmp(p.x) === 0)309 return this.curve.point(null, null);310 var c = this.y.redSub(p.y);311 if (c.cmpn(0) !== 0)312 c = c.redMul(this.x.redSub(p.x).redInvm());313 var nx = c.redSqr().redISub(this.x).redISub(p.x);314 var ny = c.redMul(this.x.redSub(nx)).redISub(this.y);315 return this.curve.point(nx, ny);316};317Point.prototype.dbl = function dbl() {318 if (this.inf)319 return this;320 var ys1 = this.y.redAdd(this.y);321 if (ys1.cmpn(0) === 0)322 return this.curve.point(null, null);323 var a = this.curve.a;324 var x2 = this.x.redSqr();325 var dyinv = ys1.redInvm();326 var c = x2.redAdd(x2).redIAdd(x2).redIAdd(a).redMul(dyinv);327 var nx = c.redSqr().redISub(this.x.redAdd(this.x));328 var ny = c.redMul(this.x.redSub(nx)).redISub(this.y);329 return this.curve.point(nx, ny);330};331Point.prototype.getX = function getX() {332 return this.x.fromRed();333};334Point.prototype.getY = function getY() {335 return this.y.fromRed();336};337Point.prototype.mul = function mul(k) {338 k = new BN(k, 16);339 if (this._hasDoubles(k))340 return this.curve._fixedNafMul(this, k);341 else if (this.curve.endo)342 return this.curve._endoWnafMulAdd([this], [k]);343 else344 return this.curve._wnafMul(this, k);345};346Point.prototype.mulAdd = function mulAdd(k1, p2, k2) {347 var points = [this, p2];348 var coeffs = [k1, k2];349 if (this.curve.endo)350 return this.curve._endoWnafMulAdd(points, coeffs);351 else352 return this.curve._wnafMulAdd(1, points, coeffs, 2);353};354Point.prototype.eq = function eq(p) {355 return this === p || this.inf === p.inf && (this.inf || this.x.cmp(p.x) === 0 && this.y.cmp(p.y) === 0);356};357Point.prototype.neg = function neg(_precompute) {358 if (this.inf)359 return this;360 var res = this.curve.point(this.x, this.y.redNeg());361 if (_precompute && this.precomputed) {362 var pre = this.precomputed;363 var negate = function(p) {364 return p.neg();365 };366 res.precomputed = {367 naf: pre.naf && {368 wnd: pre.naf.wnd,369 points: pre.naf.points.map(negate)370 },371 doubles: pre.doubles && {372 step: pre.doubles.step,373 points: pre.doubles.points.map(negate)374 }375 };376 }377 return res;378};379Point.prototype.toJ = function toJ() {380 if (this.inf)381 return this.curve.jpoint(null, null, null);382 var res = this.curve.jpoint(this.x, this.y, this.curve.one);383 return res;384};385function JPoint(curve, x, y, z) {386 Base.BasePoint.call(this, curve, 'jacobian');387 if (x === null && y === null && z === null) {388 this.x = this.curve.one;389 this.y = this.curve.one;390 this.z = new BN(0);391 } else {392 this.x = new BN(x, 16);393 this.y = new BN(y, 16);394 this.z = new BN(z, 16);395 }396 if (!this.x.red)397 this.x = this.x.toRed(this.curve.red);398 if (!this.y.red)399 this.y = this.y.toRed(this.curve.red);400 if (!this.z.red)401 this.z = this.z.toRed(this.curve.red);402 this.zOne = this.z === this.curve.one;403}404inherits(JPoint, Base.BasePoint);405ShortCurve.prototype.jpoint = function jpoint(x, y, z) {406 return new JPoint(this, x, y, z);407};408JPoint.prototype.toP = function toP() {409 if (this.isInfinity())410 return this.curve.point(null, null);411 var zinv = this.z.redInvm();412 var zinv2 = zinv.redSqr();413 var ax = this.x.redMul(zinv2);414 var ay = this.y.redMul(zinv2).redMul(zinv);415 return this.curve.point(ax, ay);416};417JPoint.prototype.neg = function neg() {418 return this.curve.jpoint(this.x, this.y.redNeg(), this.z);419};420JPoint.prototype.add = function add(p) {421 if (this.isInfinity())422 return p;423 if (p.isInfinity())424 return this;425 var pz2 = p.z.redSqr();426 var z2 = this.z.redSqr();427 var u1 = this.x.redMul(pz2);428 var u2 = p.x.redMul(z2);429 var s1 = this.y.redMul(pz2.redMul(p.z));430 var s2 = p.y.redMul(z2.redMul(this.z));431 var h = u1.redSub(u2);432 var r = s1.redSub(s2);433 if (h.cmpn(0) === 0) {434 if (r.cmpn(0) !== 0)435 return this.curve.jpoint(null, null, null);436 else437 return this.dbl();438 }439 var h2 = h.redSqr();440 var h3 = h2.redMul(h);441 var v = u1.redMul(h2);442 var nx = r.redSqr().redIAdd(h3).redISub(v).redISub(v);443 var ny = r.redMul(v.redISub(nx)).redISub(s1.redMul(h3));444 var nz = this.z.redMul(p.z).redMul(h);445 return this.curve.jpoint(nx, ny, nz);446};447JPoint.prototype.mixedAdd = function mixedAdd(p) {448 if (this.isInfinity())449 return p.toJ();450 if (p.isInfinity())451 return this;452 var z2 = this.z.redSqr();453 var u1 = this.x;454 var u2 = p.x.redMul(z2);455 var s1 = this.y;456 var s2 = p.y.redMul(z2).redMul(this.z);457 var h = u1.redSub(u2);458 var r = s1.redSub(s2);459 if (h.cmpn(0) === 0) {460 if (r.cmpn(0) !== 0)461 return this.curve.jpoint(null, null, null);462 else463 return this.dbl();464 }465 var h2 = h.redSqr();466 var h3 = h2.redMul(h);467 var v = u1.redMul(h2);468 var nx = r.redSqr().redIAdd(h3).redISub(v).redISub(v);469 var ny = r.redMul(v.redISub(nx)).redISub(s1.redMul(h3));470 var nz = this.z.redMul(h);471 return this.curve.jpoint(nx, ny, nz);472};473JPoint.prototype.dblp = function dblp(pow) {474 if (pow === 0)475 return this;476 if (this.isInfinity())477 return this;478 if (!pow)479 return this.dbl();480 if (this.curve.zeroA || this.curve.threeA) {481 var r = this;482 for (var i = 0; i < pow; i++)483 r = r.dbl();484 return r;485 }486 var a = this.curve.a;487 var tinv = this.curve.tinv;488 var jx = this.x;489 var jy = this.y;490 var jz = this.z;491 var jz4 = jz.redSqr().redSqr();492 var jyd = jy.redAdd(jy);493 for (var i = 0; i < pow; i++) {494 var jx2 = jx.redSqr();495 var jyd2 = jyd.redSqr();496 var jyd4 = jyd2.redSqr();497 var c = jx2.redAdd(jx2).redIAdd(jx2).redIAdd(a.redMul(jz4));498 var t1 = jx.redMul(jyd2);499 var nx = c.redSqr().redISub(t1.redAdd(t1));500 var t2 = t1.redISub(nx);501 var dny = c.redMul(t2);502 dny = dny.redIAdd(dny).redISub(jyd4);503 var nz = jyd.redMul(jz);504 if (i + 1 < pow)505 jz4 = jz4.redMul(jyd4);506 jx = nx;507 jz = nz;508 jyd = dny;509 }510 return this.curve.jpoint(jx, jyd.redMul(tinv), jz);511};512JPoint.prototype.dbl = function dbl() {513 if (this.isInfinity())514 return this;515 if (this.curve.zeroA)516 return this._zeroDbl();517 else if (this.curve.threeA)518 return this._threeDbl();519 else520 return this._dbl();521};522JPoint.prototype._zeroDbl = function _zeroDbl() {523 var nx;524 var ny;525 var nz;526 if (this.zOne) {527 var xx = this.x.redSqr();528 var yy = this.y.redSqr();529 var yyyy = yy.redSqr();530 var s = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy);531 s = s.redIAdd(s);532 var m = xx.redAdd(xx).redIAdd(xx);533 var t = m.redSqr().redISub(s).redISub(s);534 var yyyy8 = yyyy.redIAdd(yyyy);535 yyyy8 = yyyy8.redIAdd(yyyy8);536 yyyy8 = yyyy8.redIAdd(yyyy8);537 nx = t;538 ny = m.redMul(s.redISub(t)).redISub(yyyy8);539 nz = this.y.redAdd(this.y);540 } else {541 var a = this.x.redSqr();542 var b = this.y.redSqr();543 var c = b.redSqr();544 var d = this.x.redAdd(b).redSqr().redISub(a).redISub(c);545 d = d.redIAdd(d);546 var e = a.redAdd(a).redIAdd(a);547 var f = e.redSqr();548 var c8 = c.redIAdd(c);549 c8 = c8.redIAdd(c8);550 c8 = c8.redIAdd(c8);551 nx = f.redISub(d).redISub(d);552 ny = e.redMul(d.redISub(nx)).redISub(c8);553 nz = this.y.redMul(this.z);554 nz = nz.redIAdd(nz);555 }556 return this.curve.jpoint(nx, ny, nz);557};558JPoint.prototype._threeDbl = function _threeDbl() {559 var nx;560 var ny;561 var nz;562 if (this.zOne) {563 var xx = this.x.redSqr();564 var yy = this.y.redSqr();565 var yyyy = yy.redSqr();566 var s = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy);567 s = s.redIAdd(s);568 var m = xx.redAdd(xx).redIAdd(xx).redIAdd(this.curve.a);569 var t = m.redSqr().redISub(s).redISub(s);570 nx = t;571 var yyyy8 = yyyy.redIAdd(yyyy);572 yyyy8 = yyyy8.redIAdd(yyyy8);573 yyyy8 = yyyy8.redIAdd(yyyy8);574 ny = m.redMul(s.redISub(t)).redISub(yyyy8);575 nz = this.y.redAdd(this.y);576 } else {577 var delta = this.z.redSqr();578 var gamma = this.y.redSqr();579 var beta = this.x.redMul(gamma);580 var alpha = this.x.redSub(delta).redMul(this.x.redAdd(delta));581 alpha = alpha.redAdd(alpha).redIAdd(alpha);582 var beta4 = beta.redIAdd(beta);583 beta4 = beta4.redIAdd(beta4);584 var beta8 = beta4.redAdd(beta4);585 nx = alpha.redSqr().redISub(beta8);586 nz = this.y.redAdd(this.z).redSqr().redISub(gamma).redISub(delta);587 var ggamma8 = gamma.redSqr();588 ggamma8 = ggamma8.redIAdd(ggamma8);589 ggamma8 = ggamma8.redIAdd(ggamma8);590 ggamma8 = ggamma8.redIAdd(ggamma8);591 ny = alpha.redMul(beta4.redISub(nx)).redISub(ggamma8);592 }593 return this.curve.jpoint(nx, ny, nz);594};595JPoint.prototype._dbl = function _dbl() {596 var a = this.curve.a;597 var jx = this.x;598 var jy = this.y;599 var jz = this.z;600 var jz4 = jz.redSqr().redSqr();601 var jx2 = jx.redSqr();602 var jy2 = jy.redSqr();603 var c = jx2.redAdd(jx2).redIAdd(jx2).redIAdd(a.redMul(jz4));604 var jxd4 = jx.redAdd(jx);605 jxd4 = jxd4.redIAdd(jxd4);606 var t1 = jxd4.redMul(jy2);607 var nx = c.redSqr().redISub(t1.redAdd(t1));608 var t2 = t1.redISub(nx);609 var jyd8 = jy2.redSqr();610 jyd8 = jyd8.redIAdd(jyd8);611 jyd8 = jyd8.redIAdd(jyd8);612 jyd8 = jyd8.redIAdd(jyd8);613 var ny = c.redMul(t2).redISub(jyd8);614 var nz = jy.redAdd(jy).redMul(jz);615 return this.curve.jpoint(nx, ny, nz);616};617JPoint.prototype.trpl = function trpl() {618 if (!this.curve.zeroA)619 return this.dbl().add(this);620 var xx = this.x.redSqr();621 var yy = this.y.redSqr();622 var zz = this.z.redSqr();623 var yyyy = yy.redSqr();624 var m = xx.redAdd(xx).redIAdd(xx);625 var mm = m.redSqr();626 var e = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy);627 e = e.redIAdd(e);628 e = e.redAdd(e).redIAdd(e);629 e = e.redISub(mm);630 var ee = e.redSqr();631 var t = yyyy.redIAdd(yyyy);632 t = t.redIAdd(t);633 t = t.redIAdd(t);634 t = t.redIAdd(t);635 var u = m.redIAdd(e).redSqr().redISub(mm).redISub(ee).redISub(t);636 var yyu4 = yy.redMul(u);637 yyu4 = yyu4.redIAdd(yyu4);638 yyu4 = yyu4.redIAdd(yyu4);639 var nx = this.x.redMul(ee).redISub(yyu4);640 nx = nx.redIAdd(nx);641 nx = nx.redIAdd(nx);642 var ny = this.y.redMul(u.redMul(t.redISub(u)).redISub(e.redMul(ee)));643 ny = ny.redIAdd(ny);644 ny = ny.redIAdd(ny);645 ny = ny.redIAdd(ny);646 var nz = this.z.redAdd(e).redSqr().redISub(zz).redISub(ee);647 return this.curve.jpoint(nx, ny, nz);648};649JPoint.prototype.mul = function mul(k, kbase) {650 k = new BN(k, kbase);651 return this.curve._wnafMul(this, k);652};653JPoint.prototype.eq = function eq(p) {654 if (p.type === 'affine')655 return this.eq(p.toJ());656 if (this === p)657 return true;658 var z2 = this.z.redSqr();659 var pz2 = p.z.redSqr();660 if (this.x.redMul(pz2).redISub(p.x.redMul(z2)).cmpn(0) !== 0)661 return false;662 var z3 = z2.redMul(this.z);663 var pz3 = pz2.redMul(p.z);664 return this.y.redMul(pz3).redISub(p.y.redMul(z3)).cmpn(0) === 0;665};666JPoint.prototype.inspect = function inspect() {667 if (this.isInfinity())668 return '<EC JPoint Infinity>';669 return '<EC JPoint x: ' + this.x.toString(16, 2) + ' y: ' + this.y.toString(16, 2) + ' z: ' + this.z.toString(16, 2) + '>';670};671JPoint.prototype.isInfinity = function isInfinity() {672 return this.z.cmpn(0) === 0;...
rbtree.py
Source:rbtree.py
1class Node:2 def __init__(self, key):3 self.key = key4 self.red = True5 self.right = None6 self.left = None7 self.parent = None8class RBtree(Node):9 def __init__(self):10 self.root = None11 def insert(self, key):12 node = Node(key)13 node.red = True14 if self.root == None:15 node.red = False16 self.root = node17 node.left = Node(None)18 node.left.red = False19 node.right = Node(None)20 node.right.red = False21 return22 currentNode = self.root23 while currentNode.key != None:24 potentialParent = currentNode25 if node.key < currentNode.key:26 currentNode = currentNode.left27 else:28 currentNode = currentNode.right29 node.parent = potentialParent30 if node.key < node.parent.key:31 currentNode.left = node32 node.parent.left = node33 34 else:35 currentNode.right = node36 node.parent.right = node37 node.left = Node(None)38 node.left.red = False39 node.right = Node(None)40 node.right.red = False41 self._fixTree(node)42 def MinNode(self,key=None):43 if self.root is not None:44 current = self.root45 while (current.left.key is not None):46 current = current.left47 return current48 else:49 print("tree is empty")50 def MaxNode(self):51 if self.root is not None:52 current = self.root53 while (current.right.key is not None):54 current = current.right55 return current56 else:57 print("tree is empty")58 def search(self, key):59 if self.root is not None:60 currentNode = self.root61 while currentNode.key != None and key != currentNode.key:62 if key < currentNode.key:63 currentNode = currentNode.left64 else:65 currentNode = currentNode.right66 return currentNode67 else:68 print("tree is empty")69 def FindNext(self, x):70 current = self.search(x)71 if current:72 current = current.right73 if current.key is not None:74 while (current.left.key is not None):75 current = current.left76 return current77 else:78 print('x is not exist in tree')79 def FindPrev(self, x):80 current = self.search(x)81 if current:82 current=current.left83 if current.key is not None:84 while (current.right.key is not None):85 current = current.right86 return current87 else:88 print('x is not exist in tree')89 def deleteNode(self, key):90 currentNode = self.search(key)91 if currentNode is not self.root:92 if currentNode.key is not None:93 if currentNode == currentNode.parent.left:94 self._delete_left_node(currentNode)95 96 else:97 self._delete_right_node(currentNode)98 else:99 print("Node is not exists")100 else:101 self._delete_root_node(currentNode)102 103#________________auxiliary_methods______________104 105 def _fixTree(self, node):106 while node.parent is not None and node.parent.red == True:107 if node.parent == node.parent.parent.left:108 uncle = node.parent.parent.right109 if uncle.red:110 node.parent.red = False111 uncle.red = False112 node.parent.parent.red = True113 node = node.parent.parent114 else:115 if node == node.parent.right:116 node = node.parent117 self._left_rotate(node)118 node.parent.red = False119 node.parent.parent.red = True120 self._right_rotate(node.parent.parent)121 else:122 uncle = node.parent.parent.left123 if uncle.red:124 node.parent.red = False125 uncle.red = False126 node.parent.parent.red = True127 node = node.parent.parent128 else:129 if node == node.parent.left:130 node = node.parent131 self._right_rotate(node)132 node.parent.red = False133 node.parent.parent.red = True134 self._left_rotate(node.parent.parent)135 self.root.red = False 136 137 def _left_rotate(self, node):138 sibling = node.right139 node.right = sibling.left140 if sibling.left != None:141 sibling.left.parent = node142 sibling.parent = node.parent143 if node.parent == None:144 self.root = sibling145 else:146 if node == node.parent.left:147 node.parent.left = sibling148 else:149 node.parent.right = sibling150 sibling.left = node151 node.parent = sibling152 def _right_rotate(self, node):153 sibling = node.left154 node.left = sibling.right155 if sibling.right != None:156 sibling.right.parent = node157 sibling.parent = node.parent158 if node.parent == None:159 self.root = sibling160 else:161 if node == node.parent.right:162 node.parent.right = sibling163 else:164 node.parent.left = sibling165 sibling.right = node166 node.parent = sibling167 168 169 170 def _delete_left_node(self,currentNode):171 if currentNode.left.key is None and currentNode.right.key is None:172 self._delete_left_node_noChildren(currentNode)173 elif currentNode.left.key is None and currentNode.right.key is not None:174 self._delete_left_node_onlyRightChildren(currentNode)175 elif currentNode.left.key is not None and currentNode.right.key is None:176 self._delete_left_node_onlyLeftChildren(currentNode)177 else:178 self._delete_left_node_bothChildren(currentNode)179 180 181 182 def _delete_right_node(self,currentNode):183 if currentNode.left.key is None and currentNode.right.key is None:184 self._delete_right_node_noChildren(currentNode) 185 186 elif currentNode.left.key is None and currentNode.right.key is not None:187 self._delete_right_node_onlyRightChildren(currentNode)188 elif currentNode.left.key is not None and currentNode.right.key is None:189 self._delete_right_node_onlyLeftChildren(currentNode)190 else:191 self._delete_right_node_bothChildren(currentNode)192 193 194 def _delete_root_node(self, currentNode):195 if currentNode.left.key is None and currentNode.right.key is None:196 self.root = None197 elif currentNode.left.key is None and currentNode.right.key is not None:198 self.root=currentNode.right199 currentNode.right.parent = None200 elif currentNode.left.key is not None and currentNode.right.key is None:201 self.root = currentNode.left202 currentNode.left.parent = None203 else:204 next = self.FindNext(currentNode.key)205 next.parent = None206 self.root = next207 currentNode.left.parent = self.root208 self.root.left = currentNode.left209 self.root.red = False210 211 def _delete_left_node_noChildren(self, currentNode):212 currentNode.parent.left = currentNode.left213 currentNode.left.parent = currentNode.parent214 if currentNode.red is False:215 brother = currentNode.parent.right216 if brother.red == False:217 if brother.left.red and brother.right.red:218 brother.right.red = False219 self._left_rotate(brother.parent)220 elif brother.left.red and brother.right.red==False:221 brother.left.red = False222 brother.red = True223 self._right_rotate(brother)224 self._left_rotate(brother.parent.parent)225 elif brother.right.red and brother.left.red == False:226 brother.right.red = False227 self._left_rotate(brother.parent) 228 else:229 if brother.left.key is not None and brother.right.key is not None:230 brother.red = False231 brother.left.red = True232 self._left_rotate(brother.parent)233 234 def _delete_left_node_onlyRightChildren(self, currentNode):235 currentNode.parent.left = currentNode.right236 currentNode.right.parent = currentNode.parent237 if currentNode.red is False:238 if currentNode.right.red:239 currentNode.right.red = False240 else:241 brother = currentNode.parent.right242 if brother.red == False:243 if brother.left.red and brother.right.red:244 brother.right.red = False245 self._left_rotate(brother.parent)246 elif brother.left.red and brother.right.red==False:247 brother.left.red = False248 brother.red = True249 self._right_rotate(brother)250 self._left_rotate(brother.parent.parent)251 elif brother.right.red and brother.left.red == False:252 brother.right.red = False253 self._left_rotate(brother.parent) 254 else:255 if brother.left.key is not None and brother.right.key is not None:256 brother.red = False257 brother.left.red = True258 self._left_rotate(brother.parent)259 260 def _delete_left_node_onlyLeftChildren(self, currentNode):261 currentNode.parent.left = currentNode.left262 currentNode.left.parent = currentNode.parent263 if currentNode.red is False:264 if currentNode.left.red:265 currentNode.left.red = False266 267 def _delete_left_node_bothChildren(self, currentNode):268 next = self.FindNext(currentNode.key)269 currentNode.parent.left = next270 next.parent = currentNode.parent271 currentNode.left.parent = next272 next.left = currentNode.left273 if next.red is False:274 if next.right.red:275 next.right.red = False276 next.red = True277 else:278 next.red = False279 def _delete_right_node_noChildren(self, currentNode):280 currentNode.parent.right = currentNode.right281 currentNode.right.parent = currentNode.parent282 if currentNode.red is False:283 brother = currentNode.parent.left284 print(brother.key)285 if brother.red == False:286 if brother.left.red and brother.right.red:287 brother.right.red = False288 self._right_rotate(brother.parent)289 elif brother.right.red and brother.left.red == False:290 brother.right.red = False291 brother.red = True292 self._left_rotate(brother)293 self._right_rotate(brother.parent.parent)294 elif brother.left.red and brother.right.red == False:295 brother.left.red = False296 self._right_rotate(brother.parent)297 298 else:299 if brother.left.key is not None and brother.right.key is not None:300 brother.red = False301 brother.right.red = True302 self._right_rotate(brother.parent)303 304 def _delete_right_node_onlyRightChildren(self, currentNode):305 currentNode.parent.right = currentNode.right306 currentNode.right.parent = currentNode.parent307 if currentNode.red is False:308 if currentNode.right.red:309 currentNode.right.red = False310 311 def _delete_right_node_onlyLeftChildren(self, currentNode):312 currentNode.parent.right = currentNode.left313 currentNode.left.parent = currentNode.parent314 if currentNode.red is False:315 if currentNode.left.red:316 currentNode.left.red = False317 318 def _delete_right_node_bothChildren(self, currentNode):319 next = self.FindNext(currentNode.key)320 currentNode.parent.right = next321 next.parent = currentNode.parent322 currentNode.left.parent= next323 next.left = currentNode.left324 print(next.key)325 326 if next.red is False:327 if next.right.red: 328 next.right.red = False329 next.red = True330 else:...
edwards.js
Source:edwards.js
1/* */ 2'use strict';3var curve = require('./index');4var elliptic = require('../../elliptic');5var BN = require('bn.js');6var inherits = require('inherits');7var Base = curve.base;8var assert = elliptic.utils.assert;9function EdwardsCurve(conf) {10 this.twisted = (conf.a | 0) !== 1;11 this.mOneA = this.twisted && (conf.a | 0) === -1;12 this.extended = this.mOneA;13 Base.call(this, 'edwards', conf);14 this.a = new BN(conf.a, 16).umod(this.red.m);15 this.a = this.a.toRed(this.red);16 this.c = new BN(conf.c, 16).toRed(this.red);17 this.c2 = this.c.redSqr();18 this.d = new BN(conf.d, 16).toRed(this.red);19 this.dd = this.d.redAdd(this.d);20 assert(!this.twisted || this.c.fromRed().cmpn(1) === 0);21 this.oneC = (conf.c | 0) === 1;22}23inherits(EdwardsCurve, Base);24module.exports = EdwardsCurve;25EdwardsCurve.prototype._mulA = function _mulA(num) {26 if (this.mOneA)27 return num.redNeg();28 else29 return this.a.redMul(num);30};31EdwardsCurve.prototype._mulC = function _mulC(num) {32 if (this.oneC)33 return num;34 else35 return this.c.redMul(num);36};37EdwardsCurve.prototype.jpoint = function jpoint(x, y, z, t) {38 return this.point(x, y, z, t);39};40EdwardsCurve.prototype.pointFromX = function pointFromX(x, odd) {41 x = new BN(x, 16);42 if (!x.red)43 x = x.toRed(this.red);44 var x2 = x.redSqr();45 var rhs = this.c2.redSub(this.a.redMul(x2));46 var lhs = this.one.redSub(this.c2.redMul(this.d).redMul(x2));47 var y2 = rhs.redMul(lhs.redInvm());48 var y = y2.redSqrt();49 if (y.redSqr().redSub(y2).cmp(this.zero) !== 0)50 throw new Error('invalid point');51 var isOdd = y.fromRed().isOdd();52 if (odd && !isOdd || !odd && isOdd)53 y = y.redNeg();54 return this.point(x, y);55};56EdwardsCurve.prototype.pointFromY = function pointFromY(y, odd) {57 y = new BN(y, 16);58 if (!y.red)59 y = y.toRed(this.red);60 var y2 = y.redSqr();61 var lhs = y2.redSub(this.one);62 var rhs = y2.redMul(this.d).redAdd(this.one);63 var x2 = lhs.redMul(rhs.redInvm());64 if (x2.cmp(this.zero) === 0) {65 if (odd)66 throw new Error('invalid point');67 else68 return this.point(this.zero, y);69 }70 var x = x2.redSqrt();71 if (x.redSqr().redSub(x2).cmp(this.zero) !== 0)72 throw new Error('invalid point');73 if (x.isOdd() !== odd)74 x = x.redNeg();75 return this.point(x, y);76};77EdwardsCurve.prototype.validate = function validate(point) {78 if (point.isInfinity())79 return true;80 point.normalize();81 var x2 = point.x.redSqr();82 var y2 = point.y.redSqr();83 var lhs = x2.redMul(this.a).redAdd(y2);84 var rhs = this.c2.redMul(this.one.redAdd(this.d.redMul(x2).redMul(y2)));85 return lhs.cmp(rhs) === 0;86};87function Point(curve, x, y, z, t) {88 Base.BasePoint.call(this, curve, 'projective');89 if (x === null && y === null && z === null) {90 this.x = this.curve.zero;91 this.y = this.curve.one;92 this.z = this.curve.one;93 this.t = this.curve.zero;94 this.zOne = true;95 } else {96 this.x = new BN(x, 16);97 this.y = new BN(y, 16);98 this.z = z ? new BN(z, 16) : this.curve.one;99 this.t = t && new BN(t, 16);100 if (!this.x.red)101 this.x = this.x.toRed(this.curve.red);102 if (!this.y.red)103 this.y = this.y.toRed(this.curve.red);104 if (!this.z.red)105 this.z = this.z.toRed(this.curve.red);106 if (this.t && !this.t.red)107 this.t = this.t.toRed(this.curve.red);108 this.zOne = this.z === this.curve.one;109 if (this.curve.extended && !this.t) {110 this.t = this.x.redMul(this.y);111 if (!this.zOne)112 this.t = this.t.redMul(this.z.redInvm());113 }114 }115}116inherits(Point, Base.BasePoint);117EdwardsCurve.prototype.pointFromJSON = function pointFromJSON(obj) {118 return Point.fromJSON(this, obj);119};120EdwardsCurve.prototype.point = function point(x, y, z, t) {121 return new Point(this, x, y, z, t);122};123Point.fromJSON = function fromJSON(curve, obj) {124 return new Point(curve, obj[0], obj[1], obj[2]);125};126Point.prototype.inspect = function inspect() {127 if (this.isInfinity())128 return '<EC Point Infinity>';129 return '<EC Point x: ' + this.x.fromRed().toString(16, 2) + ' y: ' + this.y.fromRed().toString(16, 2) + ' z: ' + this.z.fromRed().toString(16, 2) + '>';130};131Point.prototype.isInfinity = function isInfinity() {132 return this.x.cmpn(0) === 0 && this.y.cmp(this.z) === 0;133};134Point.prototype._extDbl = function _extDbl() {135 var a = this.x.redSqr();136 var b = this.y.redSqr();137 var c = this.z.redSqr();138 c = c.redIAdd(c);139 var d = this.curve._mulA(a);140 var e = this.x.redAdd(this.y).redSqr().redISub(a).redISub(b);141 var g = d.redAdd(b);142 var f = g.redSub(c);143 var h = d.redSub(b);144 var nx = e.redMul(f);145 var ny = g.redMul(h);146 var nt = e.redMul(h);147 var nz = f.redMul(g);148 return this.curve.point(nx, ny, nz, nt);149};150Point.prototype._projDbl = function _projDbl() {151 var b = this.x.redAdd(this.y).redSqr();152 var c = this.x.redSqr();153 var d = this.y.redSqr();154 var nx;155 var ny;156 var nz;157 if (this.curve.twisted) {158 var e = this.curve._mulA(c);159 var f = e.redAdd(d);160 if (this.zOne) {161 nx = b.redSub(c).redSub(d).redMul(f.redSub(this.curve.two));162 ny = f.redMul(e.redSub(d));163 nz = f.redSqr().redSub(f).redSub(f);164 } else {165 var h = this.z.redSqr();166 var j = f.redSub(h).redISub(h);167 nx = b.redSub(c).redISub(d).redMul(j);168 ny = f.redMul(e.redSub(d));169 nz = f.redMul(j);170 }171 } else {172 var e = c.redAdd(d);173 var h = this.curve._mulC(this.c.redMul(this.z)).redSqr();174 var j = e.redSub(h).redSub(h);175 nx = this.curve._mulC(b.redISub(e)).redMul(j);176 ny = this.curve._mulC(e).redMul(c.redISub(d));177 nz = e.redMul(j);178 }179 return this.curve.point(nx, ny, nz);180};181Point.prototype.dbl = function dbl() {182 if (this.isInfinity())183 return this;184 if (this.curve.extended)185 return this._extDbl();186 else187 return this._projDbl();188};189Point.prototype._extAdd = function _extAdd(p) {190 var a = this.y.redSub(this.x).redMul(p.y.redSub(p.x));191 var b = this.y.redAdd(this.x).redMul(p.y.redAdd(p.x));192 var c = this.t.redMul(this.curve.dd).redMul(p.t);193 var d = this.z.redMul(p.z.redAdd(p.z));194 var e = b.redSub(a);195 var f = d.redSub(c);196 var g = d.redAdd(c);197 var h = b.redAdd(a);198 var nx = e.redMul(f);199 var ny = g.redMul(h);200 var nt = e.redMul(h);201 var nz = f.redMul(g);202 return this.curve.point(nx, ny, nz, nt);203};204Point.prototype._projAdd = function _projAdd(p) {205 var a = this.z.redMul(p.z);206 var b = a.redSqr();207 var c = this.x.redMul(p.x);208 var d = this.y.redMul(p.y);209 var e = this.curve.d.redMul(c).redMul(d);210 var f = b.redSub(e);211 var g = b.redAdd(e);212 var tmp = this.x.redAdd(this.y).redMul(p.x.redAdd(p.y)).redISub(c).redISub(d);213 var nx = a.redMul(f).redMul(tmp);214 var ny;215 var nz;216 if (this.curve.twisted) {217 ny = a.redMul(g).redMul(d.redSub(this.curve._mulA(c)));218 nz = f.redMul(g);219 } else {220 ny = a.redMul(g).redMul(d.redSub(c));221 nz = this.curve._mulC(f).redMul(g);222 }223 return this.curve.point(nx, ny, nz);224};225Point.prototype.add = function add(p) {226 if (this.isInfinity())227 return p;228 if (p.isInfinity())229 return this;230 if (this.curve.extended)231 return this._extAdd(p);232 else233 return this._projAdd(p);234};235Point.prototype.mul = function mul(k) {236 if (this._hasDoubles(k))237 return this.curve._fixedNafMul(this, k);238 else239 return this.curve._wnafMul(this, k);240};241Point.prototype.mulAdd = function mulAdd(k1, p, k2) {242 return this.curve._wnafMulAdd(1, [this, p], [k1, k2], 2);243};244Point.prototype.normalize = function normalize() {245 if (this.zOne)246 return this;247 var zi = this.z.redInvm();248 this.x = this.x.redMul(zi);249 this.y = this.y.redMul(zi);250 if (this.t)251 this.t = this.t.redMul(zi);252 this.z = this.curve.one;253 this.zOne = true;254 return this;255};256Point.prototype.neg = function neg() {257 return this.curve.point(this.x.redNeg(), this.y, this.z, this.t && this.t.redNeg());258};259Point.prototype.getX = function getX() {260 this.normalize();261 return this.x.fromRed();262};263Point.prototype.getY = function getY() {264 this.normalize();265 return this.y.fromRed();266};267Point.prototype.eq = function eq(other) {268 return this === other || this.getX().cmp(other.getX()) === 0 && this.getY().cmp(other.getY()) === 0;269};270Point.prototype.toP = Point.prototype.normalize;...
blur.py
Source:blur.py
1"""2File: blur.py3Name:4-------------------------------5This file shows the original image first,6smiley-face.png, and then compare to its7blurred image. The blur algorithm uses the8average RGB values of a pixel's nearest neighbors.9"""10from simpleimage import SimpleImage11BLUR_INDEX = 512def main():13 """14 TODO: put in a picture and show the blurred version of it15 """16 old_img = SimpleImage("images/smiley-face.png")17 old_img.show()18 blurred_img = blur(old_img)19 for i in range(BLUR_INDEX):20 blurred_img = blur(blurred_img)21 blurred_img.show()22def blur(img):23 """24 :param img: An image to be blurred25 :return: a blurred image26 """27 new_img = SimpleImage.blank(img.width, img.height)28 for x in range(img.width):29 for y in range(img.height):30 pixel = new_img.get_pixel(x, y)31 sum_red = 032 sum_blue = 033 sum_green = 034 if x == 0:35 if y == 0:36 for i in range(0, 2):37 for j in range(0, 2):38 neighbor = img.get_pixel(x + i, y + j)39 sum_red += neighbor.red40 sum_blue += neighbor.blue41 sum_green += neighbor.green42 pixel.red = sum_red / 443 pixel.blue = sum_blue / 444 pixel.green = sum_green / 445 elif y == img.height-1:46 for i in range(0, 2):47 for j in range(-1, 1):48 neighbor = img.get_pixel(x + i, y + j)49 sum_red += neighbor.red50 sum_blue += neighbor.blue51 sum_green += neighbor.green52 pixel.red = sum_red / 453 pixel.blue = sum_blue / 454 pixel.green = sum_green / 455 else:56 for i in range(0, 2):57 for j in range(-1, 2):58 neighbor = img.get_pixel(x + i, y + j)59 sum_red += neighbor.red60 sum_blue += neighbor.blue61 sum_green += neighbor.green62 pixel.red = sum_red / 663 pixel.blue = sum_blue / 664 pixel.green = sum_green / 665 elif y == 0:66 if x == img.width-1:67 for i in range(-1, 1):68 for j in range(0, 2):69 neighbor = img.get_pixel(x + i, y + j)70 sum_red += neighbor.red71 sum_blue += neighbor.blue72 sum_green += neighbor.green73 pixel.red = sum_red / 474 pixel.blue = sum_blue / 475 pixel.green = sum_green / 476 else:77 for i in range(-1, 2):78 for j in range(0, 2):79 neighbor = img.get_pixel(x + i, y + j)80 sum_red += neighbor.red81 sum_blue += neighbor.blue82 sum_green += neighbor.green83 pixel.red = sum_red / 684 pixel.blue = sum_blue / 685 pixel.green = sum_green / 686 elif x == img.width-1:87 if y == img.height-1:88 for i in range(-1, 1):89 for j in range(-1, 1):90 neighbor = img.get_pixel(x + i, y + j)91 sum_red += neighbor.red92 sum_blue += neighbor.blue93 sum_green += neighbor.green94 pixel.red = sum_red / 495 pixel.blue = sum_blue / 496 pixel.green = sum_green / 497 else:98 for i in range(-1, 1):99 for j in range(-1, 2):100 neighbor = img.get_pixel(x + i, y + j)101 sum_red += neighbor.red102 sum_blue += neighbor.blue103 sum_green += neighbor.green104 pixel.red = sum_red / 6105 pixel.blue = sum_blue / 6106 pixel.green = sum_green / 6107 elif y == img.height-1:108 for i in range(-1, 2):109 for j in range(-1, 1):110 neighbor = img.get_pixel(x + i, y + j)111 sum_red += neighbor.red112 sum_blue += neighbor.blue113 sum_green += neighbor.green114 pixel.red = sum_red / 6115 pixel.blue = sum_blue / 6116 pixel.green = sum_green / 6117 else:118 for i in range(-1, 2):119 for j in range(-1, 2):120 neighbor = img.get_pixel(x+i, y+j)121 sum_red += neighbor.red122 sum_blue += neighbor.blue123 sum_green += neighbor.green124 pixel.red = sum_red/9125 pixel.blue = sum_blue/9126 pixel.green = sum_green/9127 return new_img128# ---- DO NOT EDIT CODE BELOW THIS LINE ---- #129if __name__ == '__main__':...
Automation Testing Tutorials
Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.
LambdaTest Learning Hubs:
- JUnit Tutorial
- TestNG Tutorial
- Webdriver Tutorial
- WebDriverIO Tutorial
- Protractor Tutorial
- Selenium 4 Tutorial
- Jenkins Tutorial
- NUnit Tutorial
- Jest Tutorial
- Playwright Tutorial
- Cypress Tutorial
- PyTest Tutorial
YouTube
You could also refer to video tutorials over LambdaTest YouTube channel to get step by step demonstration from industry experts.
Run green automation tests on LambdaTest cloud grid
Perform automation testing on 3000+ real desktop and mobile devices online.
Try LambdaTest Now !!
Get 100 minutes of automation test minutes FREE!!
Was this article helpful?
