using Renci.SshNet.Security.Org.BouncyCastle.Utilities; using System; using System.Text; namespace Renci.SshNet.Security.Org.BouncyCastle.Math.EC { internal class LongArray { private static readonly ushort[] INTERLEAVE2_TABLE = new ushort[256] { 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 1024, 1025, 1028, 1029, 1040, 1041, 1044, 1045, 1088, 1089, 1092, 1093, 1104, 1105, 1108, 1109, 1280, 1281, 1284, 1285, 1296, 1297, 1300, 1301, 1344, 1345, 1348, 1349, 1360, 1361, 1364, 1365, 4096, 4097, 4100, 4101, 4112, 4113, 4116, 4117, 4160, 4161, 4164, 4165, 4176, 4177, 4180, 4181, 4352, 4353, 4356, 4357, 4368, 4369, 4372, 4373, 4416, 4417, 4420, 4421, 4432, 4433, 4436, 4437, 5120, 5121, 5124, 5125, 5136, 5137, 5140, 5141, 5184, 5185, 5188, 5189, 5200, 5201, 5204, 5205, 5376, 5377, 5380, 5381, 5392, 5393, 5396, 5397, 5440, 5441, 5444, 5445, 5456, 5457, 5460, 5461, 16384, 16385, 16388, 16389, 16400, 16401, 16404, 16405, 16448, 16449, 16452, 16453, 16464, 16465, 16468, 16469, 16640, 16641, 16644, 16645, 16656, 16657, 16660, 16661, 16704, 16705, 16708, 16709, 16720, 16721, 16724, 16725, 17408, 17409, 17412, 17413, 17424, 17425, 17428, 17429, 17472, 17473, 17476, 17477, 17488, 17489, 17492, 17493, 17664, 17665, 17668, 17669, 17680, 17681, 17684, 17685, 17728, 17729, 17732, 17733, 17744, 17745, 17748, 17749, 20480, 20481, 20484, 20485, 20496, 20497, 20500, 20501, 20544, 20545, 20548, 20549, 20560, 20561, 20564, 20565, 20736, 20737, 20740, 20741, 20752, 20753, 20756, 20757, 20800, 20801, 20804, 20805, 20816, 20817, 20820, 20821, 21504, 21505, 21508, 21509, 21520, 21521, 21524, 21525, 21568, 21569, 21572, 21573, 21584, 21585, 21588, 21589, 21760, 21761, 21764, 21765, 21776, 21777, 21780, 21781, 21824, 21825, 21828, 21829, 21840, 21841, 21844, 21845 }; private static readonly int[] INTERLEAVE3_TABLE = new int[128] { 0, 1, 8, 9, 64, 65, 72, 73, 512, 513, 520, 521, 576, 577, 584, 585, 4096, 4097, 4104, 4105, 4160, 4161, 4168, 4169, 4608, 4609, 4616, 4617, 4672, 4673, 4680, 4681, 32768, 32769, 32776, 32777, 32832, 32833, 32840, 32841, 33280, 33281, 33288, 33289, 33344, 33345, 33352, 33353, 36864, 36865, 36872, 36873, 36928, 36929, 36936, 36937, 37376, 37377, 37384, 37385, 37440, 37441, 37448, 37449, 262144, 262145, 262152, 262153, 262208, 262209, 262216, 262217, 262656, 262657, 262664, 262665, 262720, 262721, 262728, 262729, 266240, 266241, 266248, 266249, 266304, 266305, 266312, 266313, 266752, 266753, 266760, 266761, 266816, 266817, 266824, 266825, 294912, 294913, 294920, 294921, 294976, 294977, 294984, 294985, 295424, 295425, 295432, 295433, 295488, 295489, 295496, 295497, 299008, 299009, 299016, 299017, 299072, 299073, 299080, 299081, 299520, 299521, 299528, 299529, 299584, 299585, 299592, 299593 }; private static readonly int[] INTERLEAVE4_TABLE = new int[256] { 0, 1, 16, 17, 256, 257, 272, 273, 4096, 4097, 4112, 4113, 4352, 4353, 4368, 4369, 65536, 65537, 65552, 65553, 65792, 65793, 65808, 65809, 69632, 69633, 69648, 69649, 69888, 69889, 69904, 69905, 1048576, 1048577, 1048592, 1048593, 1048832, 1048833, 1048848, 1048849, 1052672, 1052673, 1052688, 1052689, 1052928, 1052929, 1052944, 1052945, 1114112, 1114113, 1114128, 1114129, 1114368, 1114369, 1114384, 1114385, 1118208, 1118209, 1118224, 1118225, 1118464, 1118465, 1118480, 1118481, 16777216, 16777217, 16777232, 16777233, 16777472, 16777473, 16777488, 16777489, 16781312, 16781313, 16781328, 16781329, 16781568, 16781569, 16781584, 16781585, 16842752, 16842753, 16842768, 16842769, 16843008, 16843009, 16843024, 16843025, 16846848, 16846849, 16846864, 16846865, 16847104, 16847105, 16847120, 16847121, 17825792, 17825793, 17825808, 17825809, 17826048, 17826049, 17826064, 17826065, 17829888, 17829889, 17829904, 17829905, 17830144, 17830145, 17830160, 17830161, 17891328, 17891329, 17891344, 17891345, 17891584, 17891585, 17891600, 17891601, 17895424, 17895425, 17895440, 17895441, 17895680, 17895681, 17895696, 17895697, 268435456, 268435457, 268435472, 268435473, 268435712, 268435713, 268435728, 268435729, 268439552, 268439553, 268439568, 268439569, 268439808, 268439809, 268439824, 268439825, 268500992, 268500993, 268501008, 268501009, 268501248, 268501249, 268501264, 268501265, 268505088, 268505089, 268505104, 268505105, 268505344, 268505345, 268505360, 268505361, 269484032, 269484033, 269484048, 269484049, 269484288, 269484289, 269484304, 269484305, 269488128, 269488129, 269488144, 269488145, 269488384, 269488385, 269488400, 269488401, 269549568, 269549569, 269549584, 269549585, 269549824, 269549825, 269549840, 269549841, 269553664, 269553665, 269553680, 269553681, 269553920, 269553921, 269553936, 269553937, 285212672, 285212673, 285212688, 285212689, 285212928, 285212929, 285212944, 285212945, 285216768, 285216769, 285216784, 285216785, 285217024, 285217025, 285217040, 285217041, 285278208, 285278209, 285278224, 285278225, 285278464, 285278465, 285278480, 285278481, 285282304, 285282305, 285282320, 285282321, 285282560, 285282561, 285282576, 285282577, 286261248, 286261249, 286261264, 286261265, 286261504, 286261505, 286261520, 286261521, 286265344, 286265345, 286265360, 286265361, 286265600, 286265601, 286265616, 286265617, 286326784, 286326785, 286326800, 286326801, 286327040, 286327041, 286327056, 286327057, 286330880, 286330881, 286330896, 286330897, 286331136, 286331137, 286331152, 286331153 }; private static readonly int[] INTERLEAVE5_TABLE = new int[128] { 0, 1, 32, 33, 1024, 1025, 1056, 1057, 32768, 32769, 32800, 32801, 33792, 33793, 33824, 33825, 1048576, 1048577, 1048608, 1048609, 1049600, 1049601, 1049632, 1049633, 1081344, 1081345, 1081376, 1081377, 1082368, 1082369, 1082400, 1082401, 33554432, 33554433, 33554464, 33554465, 33555456, 33555457, 33555488, 33555489, 33587200, 33587201, 33587232, 33587233, 33588224, 33588225, 33588256, 33588257, 34603008, 34603009, 34603040, 34603041, 34604032, 34604033, 34604064, 34604065, 34635776, 34635777, 34635808, 34635809, 34636800, 34636801, 34636832, 34636833, 1073741824, 1073741825, 1073741856, 1073741857, 1073742848, 1073742849, 1073742880, 1073742881, 1073774592, 1073774593, 1073774624, 1073774625, 1073775616, 1073775617, 1073775648, 1073775649, 1074790400, 1074790401, 1074790432, 1074790433, 1074791424, 1074791425, 1074791456, 1074791457, 1074823168, 1074823169, 1074823200, 1074823201, 1074824192, 1074824193, 1074824224, 1074824225, 1107296256, 1107296257, 1107296288, 1107296289, 1107297280, 1107297281, 1107297312, 1107297313, 1107329024, 1107329025, 1107329056, 1107329057, 1107330048, 1107330049, 1107330080, 1107330081, 1108344832, 1108344833, 1108344864, 1108344865, 1108345856, 1108345857, 1108345888, 1108345889, 1108377600, 1108377601, 1108377632, 1108377633, 1108378624, 1108378625, 1108378656, 1108378657 }; private static readonly long[] INTERLEAVE7_TABLE = new long[512] { 0, 1, 128, 129, 16384, 16385, 16512, 16513, 2097152, 2097153, 2097280, 2097281, 2113536, 2113537, 2113664, 2113665, 268435456, 268435457, 268435584, 268435585, 268451840, 268451841, 268451968, 268451969, 270532608, 270532609, 270532736, 270532737, 270548992, 270548993, 270549120, 270549121, 34359738368, 34359738369, 34359738496, 34359738497, 34359754752, 34359754753, 34359754880, 34359754881, 34361835520, 34361835521, 34361835648, 34361835649, 34361851904, 34361851905, 34361852032, 34361852033, 34628173824, 34628173825, 34628173952, 34628173953, 34628190208, 34628190209, 34628190336, 34628190337, 34630270976, 34630270977, 34630271104, 34630271105, 34630287360, 34630287361, 34630287488, 34630287489, 4398046511104, 4398046511105, 4398046511232, 4398046511233, 4398046527488, 4398046527489, 4398046527616, 4398046527617, 4398048608256, 4398048608257, 4398048608384, 4398048608385, 4398048624640, 4398048624641, 4398048624768, 4398048624769, 4398314946560, 4398314946561, 4398314946688, 4398314946689, 4398314962944, 4398314962945, 4398314963072, 4398314963073, 4398317043712, 4398317043713, 4398317043840, 4398317043841, 4398317060096, 4398317060097, 4398317060224, 4398317060225, 4432406249472, 4432406249473, 4432406249600, 4432406249601, 4432406265856, 4432406265857, 4432406265984, 4432406265985, 4432408346624, 4432408346625, 4432408346752, 4432408346753, 4432408363008, 4432408363009, 4432408363136, 4432408363137, 4432674684928, 4432674684929, 4432674685056, 4432674685057, 4432674701312, 4432674701313, 4432674701440, 4432674701441, 4432676782080, 4432676782081, 4432676782208, 4432676782209, 4432676798464, 4432676798465, 4432676798592, 4432676798593, 562949953421312, 562949953421313, 562949953421440, 562949953421441, 562949953437696, 562949953437697, 562949953437824, 562949953437825, 562949955518464, 562949955518465, 562949955518592, 562949955518593, 562949955534848, 562949955534849, 562949955534976, 562949955534977, 562950221856768, 562950221856769, 562950221856896, 562950221856897, 562950221873152, 562950221873153, 562950221873280, 562950221873281, 562950223953920, 562950223953921, 562950223954048, 562950223954049, 562950223970304, 562950223970305, 562950223970432, 562950223970433, 562984313159680, 562984313159681, 562984313159808, 562984313159809, 562984313176064, 562984313176065, 562984313176192, 562984313176193, 562984315256832, 562984315256833, 562984315256960, 562984315256961, 562984315273216, 562984315273217, 562984315273344, 562984315273345, 562984581595136, 562984581595137, 562984581595264, 562984581595265, 562984581611520, 562984581611521, 562984581611648, 562984581611649, 562984583692288, 562984583692289, 562984583692416, 562984583692417, 562984583708672, 562984583708673, 562984583708800, 562984583708801, 567347999932416, 567347999932417, 567347999932544, 567347999932545, 567347999948800, 567347999948801, 567347999948928, 567347999948929, 567348002029568, 567348002029569, 567348002029696, 567348002029697, 567348002045952, 567348002045953, 567348002046080, 567348002046081, 567348268367872, 567348268367873, 567348268368000, 567348268368001, 567348268384256, 567348268384257, 567348268384384, 567348268384385, 567348270465024, 567348270465025, 567348270465152, 567348270465153, 567348270481408, 567348270481409, 567348270481536, 567348270481537, 567382359670784, 567382359670785, 567382359670912, 567382359670913, 567382359687168, 567382359687169, 567382359687296, 567382359687297, 567382361767936, 567382361767937, 567382361768064, 567382361768065, 567382361784320, 567382361784321, 567382361784448, 567382361784449, 567382628106240, 567382628106241, 567382628106368, 567382628106369, 567382628122624, 567382628122625, 567382628122752, 567382628122753, 567382630203392, 567382630203393, 567382630203520, 567382630203521, 567382630219776, 567382630219777, 567382630219904, 567382630219905, 72057594037927936, 72057594037927937, 72057594037928064, 72057594037928065, 72057594037944320, 72057594037944321, 72057594037944448, 72057594037944449, 72057594040025088, 72057594040025089, 72057594040025216, 72057594040025217, 72057594040041472, 72057594040041473, 72057594040041600, 72057594040041601, 72057594306363392, 72057594306363393, 72057594306363520, 72057594306363521, 72057594306379776, 72057594306379777, 72057594306379904, 72057594306379905, 72057594308460544, 72057594308460545, 72057594308460672, 72057594308460673, 72057594308476928, 72057594308476929, 72057594308477056, 72057594308477057, 72057628397666304, 72057628397666305, 72057628397666432, 72057628397666433, 72057628397682688, 72057628397682689, 72057628397682816, 72057628397682817, 72057628399763456, 72057628399763457, 72057628399763584, 72057628399763585, 72057628399779840, 72057628399779841, 72057628399779968, 72057628399779969, 72057628666101760, 72057628666101761, 72057628666101888, 72057628666101889, 72057628666118144, 72057628666118145, 72057628666118272, 72057628666118273, 72057628668198912, 72057628668198913, 72057628668199040, 72057628668199041, 72057628668215296, 72057628668215297, 72057628668215424, 72057628668215425, 72061992084439040, 72061992084439041, 72061992084439168, 72061992084439169, 72061992084455424, 72061992084455425, 72061992084455552, 72061992084455553, 72061992086536192, 72061992086536193, 72061992086536320, 72061992086536321, 72061992086552576, 72061992086552577, 72061992086552704, 72061992086552705, 72061992352874496, 72061992352874497, 72061992352874624, 72061992352874625, 72061992352890880, 72061992352890881, 72061992352891008, 72061992352891009, 72061992354971648, 72061992354971649, 72061992354971776, 72061992354971777, 72061992354988032, 72061992354988033, 72061992354988160, 72061992354988161, 72062026444177408, 72062026444177409, 72062026444177536, 72062026444177537, 72062026444193792, 72062026444193793, 72062026444193920, 72062026444193921, 72062026446274560, 72062026446274561, 72062026446274688, 72062026446274689, 72062026446290944, 72062026446290945, 72062026446291072, 72062026446291073, 72062026712612864, 72062026712612865, 72062026712612992, 72062026712612993, 72062026712629248, 72062026712629249, 72062026712629376, 72062026712629377, 72062026714710016, 72062026714710017, 72062026714710144, 72062026714710145, 72062026714726400, 72062026714726401, 72062026714726528, 72062026714726529, 72620543991349248, 72620543991349249, 72620543991349376, 72620543991349377, 72620543991365632, 72620543991365633, 72620543991365760, 72620543991365761, 72620543993446400, 72620543993446401, 72620543993446528, 72620543993446529, 72620543993462784, 72620543993462785, 72620543993462912, 72620543993462913, 72620544259784704, 72620544259784705, 72620544259784832, 72620544259784833, 72620544259801088, 72620544259801089, 72620544259801216, 72620544259801217, 72620544261881856, 72620544261881857, 72620544261881984, 72620544261881985, 72620544261898240, 72620544261898241, 72620544261898368, 72620544261898369, 72620578351087616, 72620578351087617, 72620578351087744, 72620578351087745, 72620578351104000, 72620578351104001, 72620578351104128, 72620578351104129, 72620578353184768, 72620578353184769, 72620578353184896, 72620578353184897, 72620578353201152, 72620578353201153, 72620578353201280, 72620578353201281, 72620578619523072, 72620578619523073, 72620578619523200, 72620578619523201, 72620578619539456, 72620578619539457, 72620578619539584, 72620578619539585, 72620578621620224, 72620578621620225, 72620578621620352, 72620578621620353, 72620578621636608, 72620578621636609, 72620578621636736, 72620578621636737, 72624942037860352, 72624942037860353, 72624942037860480, 72624942037860481, 72624942037876736, 72624942037876737, 72624942037876864, 72624942037876865, 72624942039957504, 72624942039957505, 72624942039957632, 72624942039957633, 72624942039973888, 72624942039973889, 72624942039974016, 72624942039974017, 72624942306295808, 72624942306295809, 72624942306295936, 72624942306295937, 72624942306312192, 72624942306312193, 72624942306312320, 72624942306312321, 72624942308392960, 72624942308392961, 72624942308393088, 72624942308393089, 72624942308409344, 72624942308409345, 72624942308409472, 72624942308409473, 72624976397598720, 72624976397598721, 72624976397598848, 72624976397598849, 72624976397615104, 72624976397615105, 72624976397615232, 72624976397615233, 72624976399695872, 72624976399695873, 72624976399696000, 72624976399696001, 72624976399712256, 72624976399712257, 72624976399712384, 72624976399712385, 72624976666034176, 72624976666034177, 72624976666034304, 72624976666034305, 72624976666050560, 72624976666050561, 72624976666050688, 72624976666050689, 72624976668131328, 72624976668131329, 72624976668131456, 72624976668131457, 72624976668147712, 72624976668147713, 72624976668147840, 72624976668147841 }; private const string ZEROES = "0000000000000000000000000000000000000000000000000000000000000000"; internal static readonly byte[] BitLengths = new byte[256] { 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 }; private long[] m_ints; public int Length => m_ints.Length; public LongArray(int intLen) { m_ints = new long[intLen]; } public LongArray(long[] ints) { m_ints = ints; } public LongArray(long[] ints, int off, int len) { if (off == 0 && len == ints.Length) m_ints = ints; else { m_ints = new long[len]; Array.Copy(ints, off, m_ints, 0, len); } } public LongArray(BigInteger bigInt) { if (bigInt == null || bigInt.SignValue < 0) throw new ArgumentException("invalid F2m field value", "bigInt"); if (bigInt.SignValue == 0) m_ints = new long[1]; else { byte[] array = bigInt.ToByteArray(); int num = array.Length; int num2 = 0; if (array[0] == 0) { num--; num2 = 1; } int num3 = (num + 7) / 8; m_ints = new long[num3]; int num4 = num3 - 1; int num5 = num % 8 + num2; long num6 = 0; int i = num2; if (num2 < num5) { for (; i < num5; i++) { num6 <<= 8; uint num7 = array[i]; num6 |= num7; } m_ints[num4--] = num6; } while (num4 >= 0) { num6 = 0; for (int j = 0; j < 8; j++) { num6 <<= 8; uint num10 = array[i++]; num6 |= num10; } m_ints[num4] = num6; num4--; } } } internal void CopyTo(long[] z, int zOff) { Array.Copy(m_ints, 0, z, zOff, m_ints.Length); } public bool IsOne() { long[] ints = m_ints; if (ints[0] != 1) return false; for (int i = 1; i < ints.Length; i++) { if (ints[i] != 0) return false; } return true; } public bool IsZero() { long[] ints = m_ints; for (int i = 0; i < ints.Length; i++) { if (ints[i] != 0) return false; } return true; } public int GetUsedLength() { return GetUsedLengthFrom(m_ints.Length); } public int GetUsedLengthFrom(int from) { long[] ints = m_ints; from = System.Math.Min(from, ints.Length); if (from < 1) return 0; if (ints[0] != 0) { while (ints[--from] == 0) { } return from + 1; } do { if (ints[--from] != 0) return from + 1; } while (from > 0); return 0; } public int Degree() { int num = m_ints.Length; long num2; do { if (num == 0) return 0; num2 = m_ints[--num]; } while (num2 == 0); return (num << 6) + BitLength(num2); } private int DegreeFrom(int limit) { int num = (int)((uint)(limit + 62) >> 6); long num2; do { if (num == 0) return 0; num2 = m_ints[--num]; } while (num2 == 0); return (num << 6) + BitLength(num2); } private static int BitLength(long w) { int num = (int)((ulong)w >> 32); int num2; if (num == 0) { num = (int)w; num2 = 0; } else num2 = 32; int num3 = (int)((uint)num >> 16); int num4; if (num3 == 0) { num3 = (int)((uint)num >> 8); num4 = ((num3 == 0) ? BitLengths[num] : (8 + BitLengths[num3])); } else { int num5 = (int)((uint)num3 >> 8); num4 = ((num5 == 0) ? (16 + BitLengths[num3]) : (24 + BitLengths[num5])); } return num2 + num4; } private long[] ResizedInts(int newLen) { long[] array = new long[newLen]; Array.Copy(m_ints, 0, array, 0, System.Math.Min(m_ints.Length, newLen)); return array; } public BigInteger ToBigInteger() { int usedLength = GetUsedLength(); if (usedLength == 0) return BigInteger.Zero; long num = m_ints[usedLength - 1]; byte[] array = new byte[8]; int num2 = 0; bool flag = false; for (int num3 = 7; num3 >= 0; num3--) { byte b = (byte)((ulong)num >> 8 * num3); if (flag || b != 0) { flag = true; array[num2++] = b; } } byte[] array2 = new byte[8 * (usedLength - 1) + num2]; for (int i = 0; i < num2; i++) { array2[i] = array[i]; } for (int num5 = usedLength - 2; num5 >= 0; num5--) { long num6 = m_ints[num5]; for (int num7 = 7; num7 >= 0; num7--) { array2[num2++] = (byte)((ulong)num6 >> 8 * num7); } } return new BigInteger(1, array2); } private static long ShiftUp(long[] x, int xOff, int count, int shift) { int num = 64 - shift; long num2 = 0; for (int i = 0; i < count; i++) { long num3 = x[xOff + i]; x[xOff + i] = ((num3 << shift) | num2); num2 = (long)((ulong)num3 >> num); } return num2; } private static long ShiftUp(long[] x, int xOff, long[] z, int zOff, int count, int shift) { int num = 64 - shift; long num2 = 0; for (int i = 0; i < count; i++) { long num3 = x[xOff + i]; z[zOff + i] = ((num3 << shift) | num2); num2 = (long)((ulong)num3 >> num); } return num2; } public LongArray AddOne() { if (m_ints.Length == 0) return new LongArray(new long[1] { 1 }); int newLen = System.Math.Max(1, GetUsedLength()); long[] array = ResizedInts(newLen); array[0] ^= 1; return new LongArray(array); } private void AddShiftedByBitsSafe(LongArray other, int otherDegree, int bits) { int num = (int)((uint)(otherDegree + 63) >> 6); int num2 = (int)((uint)bits >> 6); int num3 = bits & 63; if (num3 == 0) Add(m_ints, num2, other.m_ints, 0, num); else { long num4 = AddShiftedUp(m_ints, num2, other.m_ints, 0, num, num3); if (num4 != 0) m_ints[num + num2] ^= num4; } } private static long AddShiftedUp(long[] x, int xOff, long[] y, int yOff, int count, int shift) { int num = 64 - shift; long num2 = 0; for (int i = 0; i < count; i++) { long num3 = y[yOff + i]; x[xOff + i] ^= ((num3 << shift) | num2); num2 = (long)((ulong)num3 >> num); } return num2; } private static long AddShiftedDown(long[] x, int xOff, long[] y, int yOff, int count, int shift) { int num = 64 - shift; long num2 = 0; int num3 = count; while (--num3 >= 0) { long num4 = y[yOff + num3]; x[xOff + num3] ^= ((long)((ulong)num4 >> shift) | num2); num2 = num4 << num; } return num2; } public void AddShiftedByWords(LongArray other, int words) { int usedLength = other.GetUsedLength(); if (usedLength != 0) { int num = usedLength + words; if (num > m_ints.Length) m_ints = ResizedInts(num); Add(m_ints, words, other.m_ints, 0, usedLength); } } private static void Add(long[] x, int xOff, long[] y, int yOff, int count) { for (int i = 0; i < count; i++) { x[xOff + i] ^= y[yOff + i]; } } private static void Add(long[] x, int xOff, long[] y, int yOff, long[] z, int zOff, int count) { for (int i = 0; i < count; i++) { z[zOff + i] = (x[xOff + i] ^ y[yOff + i]); } } private static void AddBoth(long[] x, int xOff, long[] y1, int y1Off, long[] y2, int y2Off, int count) { for (int i = 0; i < count; i++) { x[xOff + i] ^= (y1[y1Off + i] ^ y2[y2Off + i]); } } private static void Distribute(long[] x, int src, int dst1, int dst2, int count) { for (int i = 0; i < count; i++) { long num = x[src + i]; x[dst1 + i] ^= num; x[dst2 + i] ^= num; } } private static void FlipWord(long[] buf, int off, int bit, long word) { int num = off + (int)((uint)bit >> 6); int num2 = bit & 63; if (num2 == 0) buf[num] ^= word; else { buf[num] ^= word << num2; word = (long)((ulong)word >> 64 - num2); if (word != 0) buf[++num] ^= word; } } public bool TestBitZero() { if (m_ints.Length != 0) return (m_ints[0] & 1) != 0; return false; } private static bool TestBit(long[] buf, int off, int n) { int num = (int)((uint)n >> 6); int num2 = n & 63; long num3 = 1 << num2; return (buf[off + num] & num3) != 0; } private static void FlipBit(long[] buf, int off, int n) { int num = (int)((uint)n >> 6); int num2 = n & 63; long num3 = 1 << num2; buf[off + num] ^= num3; } private static void MultiplyWord(long a, long[] b, int bLen, long[] c, int cOff) { if ((a & 1) != 0) Add(c, cOff, b, 0, bLen); int num = 1; while ((a = (long)((ulong)a >> 1)) != 0) { if ((a & 1) != 0) { long num2 = AddShiftedUp(c, cOff, b, 0, bLen, num); if (num2 != 0) c[cOff + bLen] ^= num2; } num++; } } public LongArray ModMultiplyLD(LongArray other, int m, int[] ks) { int num = Degree(); if (num == 0) return this; int num2 = other.Degree(); if (num2 == 0) return other; LongArray longArray = this; LongArray longArray2 = other; if (num > num2) { longArray = other; longArray2 = this; int num3 = num; num = num2; num2 = num3; } int num4 = (int)((uint)(num + 63) >> 6); int num5 = (int)((uint)(num2 + 63) >> 6); int num6 = (int)((uint)(num + num2 + 62) >> 6); if (num4 == 1) { long num7 = longArray.m_ints[0]; if (num7 == 1) return longArray2; long[] array = new long[num6]; MultiplyWord(num7, longArray2.m_ints, num5, array, 0); return ReduceResult(array, 0, num6, m, ks); } int num8 = (int)((uint)(num2 + 7 + 63) >> 6); int[] array2 = new int[16]; long[] array3 = new long[num8 << 4]; int num9 = array2[1] = num8; Array.Copy(longArray2.m_ints, 0, array3, num9, num5); for (int i = 2; i < 16; i++) { num9 = (array2[i] = num9 + num8); if ((i & 1) == 0) ShiftUp(array3, (int)((uint)num9 >> 1), array3, num9, num8, 1); else Add(array3, num8, array3, num9 - num8, array3, num9, num8); } long[] array4 = new long[array3.Length]; ShiftUp(array3, 0, array4, 0, array3.Length, 4); long[] ints = longArray.m_ints; long[] array5 = new long[num6]; int num10 = 15; for (int num11 = 56; num11 >= 0; num11 -= 8) { for (int j = 1; j < num4; j += 2) { int num12 = (int)((ulong)ints[j] >> num11); int num13 = num12 & num10; int num14 = (int)((uint)num12 >> 4) & num10; AddBoth(array5, j - 1, array3, array2[num13], array4, array2[num14], num8); } ShiftUp(array5, 0, num6, 8); } for (int num15 = 56; num15 >= 0; num15 -= 8) { for (int k = 0; k < num4; k += 2) { int num16 = (int)((ulong)ints[k] >> num15); int num17 = num16 & num10; int num18 = (int)((uint)num16 >> 4) & num10; AddBoth(array5, k, array3, array2[num17], array4, array2[num18], num8); } if (num15 > 0) ShiftUp(array5, 0, num6, 8); } return ReduceResult(array5, 0, num6, m, ks); } public LongArray ModMultiply(LongArray other, int m, int[] ks) { int num = Degree(); if (num == 0) return this; int num2 = other.Degree(); if (num2 == 0) return other; LongArray longArray = this; LongArray longArray2 = other; if (num > num2) { longArray = other; longArray2 = this; int num3 = num; num = num2; num2 = num3; } int num4 = (int)((uint)(num + 63) >> 6); int num5 = (int)((uint)(num2 + 63) >> 6); int num6 = (int)((uint)(num + num2 + 62) >> 6); if (num4 == 1) { long num7 = longArray.m_ints[0]; if (num7 == 1) return longArray2; long[] array = new long[num6]; MultiplyWord(num7, longArray2.m_ints, num5, array, 0); return ReduceResult(array, 0, num6, m, ks); } int num8 = (int)((uint)(num2 + 7 + 63) >> 6); int[] array2 = new int[16]; long[] array3 = new long[num8 << 4]; int num9 = array2[1] = num8; Array.Copy(longArray2.m_ints, 0, array3, num9, num5); for (int i = 2; i < 16; i++) { num9 = (array2[i] = num9 + num8); if ((i & 1) == 0) ShiftUp(array3, (int)((uint)num9 >> 1), array3, num9, num8, 1); else Add(array3, num8, array3, num9 - num8, array3, num9, num8); } long[] array4 = new long[array3.Length]; ShiftUp(array3, 0, array4, 0, array3.Length, 4); long[] ints = longArray.m_ints; long[] array5 = new long[num6 << 3]; int num10 = 15; for (int j = 0; j < num4; j++) { long num11 = ints[j]; int num12 = j; while (true) { int num13 = (int)num11 & num10; num11 = (long)((ulong)num11 >> 4); int num14 = (int)num11 & num10; AddBoth(array5, num12, array3, array2[num13], array4, array2[num14], num8); num11 = (long)((ulong)num11 >> 4); if (num11 == 0) break; num12 += num6; } } int num15 = array5.Length; while ((num15 -= num6) != 0) { AddShiftedUp(array5, num15 - num6, array5, num15, num6, 8); } return ReduceResult(array5, 0, num6, m, ks); } public LongArray ModMultiplyAlt(LongArray other, int m, int[] ks) { int num = Degree(); if (num == 0) return this; int num2 = other.Degree(); if (num2 == 0) return other; LongArray longArray = this; LongArray longArray2 = other; if (num > num2) { longArray = other; longArray2 = this; int num3 = num; num = num2; num2 = num3; } int num4 = (int)((uint)(num + 63) >> 6); int num5 = (int)((uint)(num2 + 63) >> 6); int num6 = (int)((uint)(num + num2 + 62) >> 6); if (num4 == 1) { long num7 = longArray.m_ints[0]; if (num7 == 1) return longArray2; long[] array = new long[num6]; MultiplyWord(num7, longArray2.m_ints, num5, array, 0); return ReduceResult(array, 0, num6, m, ks); } int num8 = 4; int num9 = 16; int num10 = 64; int num11 = 8; int num12 = (num10 < 64) ? num9 : (num9 - 1); int num13 = (int)((uint)(num2 + num12 + 63) >> 6); int num14 = num13 * num11; int num15 = num8 * num11; int[] array2 = new int[1 << num8]; int num16 = array2[1] = (array2[0] = num4) + num14; for (int i = 2; i < array2.Length; i++) { num16 = (array2[i] = num16 + num6); } num16 += num6; num16++; long[] array3 = new long[num16]; Interleave(longArray.m_ints, 0, array3, 0, num4, num8); int num17 = num4; Array.Copy(longArray2.m_ints, 0, array3, num17, num5); for (int j = 1; j < num11; j++) { ShiftUp(array3, num4, array3, num17 += num13, num13, j); } int num18 = (1 << num8) - 1; int num19 = 0; while (true) { int num20 = 0; do { long num21 = (long)((ulong)array3[num20] >> num19); int num22 = 0; int num23 = num4; while (true) { int num24 = (int)num21 & num18; if (num24 != 0) Add(array3, num20 + array2[num24], array3, num23, num13); if (++num22 == num11) break; num23 += num13; num21 = (long)((ulong)num21 >> num8); } } while (++num20 < num4); if ((num19 += num15) >= num10) { if (num19 >= 64) break; num19 = 64 - num8; num18 &= num18 << num10 - num19; } ShiftUp(array3, num4, num14, num11); } int num25 = array2.Length; while (--num25 > 1) { if (((long)num25 & 1) == 0) AddShiftedUp(array3, array2[(uint)num25 >> 1], array3, array2[num25], num6, num9); else Distribute(array3, array2[num25], array2[num25 - 1], array2[1], num6); } return ReduceResult(array3, array2[1], num6, m, ks); } public LongArray ModReduce(int m, int[] ks) { long[] array = Arrays.Clone(m_ints); int len = ReduceInPlace(array, 0, array.Length, m, ks); return new LongArray(array, 0, len); } public LongArray Multiply(LongArray other, int m, int[] ks) { int num = Degree(); if (num == 0) return this; int num2 = other.Degree(); if (num2 == 0) return other; LongArray longArray = this; LongArray longArray2 = other; if (num > num2) { longArray = other; longArray2 = this; int num3 = num; num = num2; num2 = num3; } int num4 = (int)((uint)(num + 63) >> 6); int num5 = (int)((uint)(num2 + 63) >> 6); int num6 = (int)((uint)(num + num2 + 62) >> 6); if (num4 == 1) { long num7 = longArray.m_ints[0]; if (num7 == 1) return longArray2; long[] array = new long[num6]; MultiplyWord(num7, longArray2.m_ints, num5, array, 0); return new LongArray(array, 0, num6); } int num8 = (int)((uint)(num2 + 7 + 63) >> 6); int[] array2 = new int[16]; long[] array3 = new long[num8 << 4]; int num9 = array2[1] = num8; Array.Copy(longArray2.m_ints, 0, array3, num9, num5); for (int i = 2; i < 16; i++) { num9 = (array2[i] = num9 + num8); if ((i & 1) == 0) ShiftUp(array3, (int)((uint)num9 >> 1), array3, num9, num8, 1); else Add(array3, num8, array3, num9 - num8, array3, num9, num8); } long[] array4 = new long[array3.Length]; ShiftUp(array3, 0, array4, 0, array3.Length, 4); long[] ints = longArray.m_ints; long[] array5 = new long[num6 << 3]; int num10 = 15; for (int j = 0; j < num4; j++) { long num11 = ints[j]; int num12 = j; while (true) { int num13 = (int)num11 & num10; num11 = (long)((ulong)num11 >> 4); int num14 = (int)num11 & num10; AddBoth(array5, num12, array3, array2[num13], array4, array2[num14], num8); num11 = (long)((ulong)num11 >> 4); if (num11 == 0) break; num12 += num6; } } int num15 = array5.Length; while ((num15 -= num6) != 0) { AddShiftedUp(array5, num15 - num6, array5, num15, num6, 8); } return new LongArray(array5, 0, num6); } public void Reduce(int m, int[] ks) { long[] ints = m_ints; int num = ReduceInPlace(ints, 0, ints.Length, m, ks); if (num < ints.Length) { m_ints = new long[num]; Array.Copy(ints, 0, m_ints, 0, num); } } private static LongArray ReduceResult(long[] buf, int off, int len, int m, int[] ks) { int len2 = ReduceInPlace(buf, off, len, m, ks); return new LongArray(buf, off, len2); } private static int ReduceInPlace(long[] buf, int off, int len, int m, int[] ks) { int num = m + 63 >> 6; if (len < num) return len; int num2 = System.Math.Min(len << 6, (m << 1) - 1); int num3; for (num3 = (len << 6) - num2; num3 >= 64; num3 -= 64) { len--; } int num4 = ks.Length; int num5 = ks[num4 - 1]; int num6 = (num4 > 1) ? ks[num4 - 2] : 0; int num7 = System.Math.Max(m, num5 + 64); int num8 = num3 + System.Math.Min(num2 - num7, m - num6) >> 6; if (num8 > 1) { int num9 = len - num8; ReduceVectorWise(buf, off, len, num9, m, ks); while (len > num9) { buf[off + --len] = 0; } num2 = num9 << 6; } if (num2 > num7) { ReduceWordWise(buf, off, len, num7, m, ks); num2 = num7; } if (num2 > m) ReduceBitWise(buf, off, num2, m, ks); return num; } private static void ReduceBitWise(long[] buf, int off, int BitLength, int m, int[] ks) { while (--BitLength >= m) { if (TestBit(buf, off, BitLength)) ReduceBit(buf, off, BitLength, m, ks); } } private static void ReduceBit(long[] buf, int off, int bit, int m, int[] ks) { FlipBit(buf, off, bit); int num = bit - m; int num2 = ks.Length; while (--num2 >= 0) { FlipBit(buf, off, ks[num2] + num); } FlipBit(buf, off, num); } private static void ReduceWordWise(long[] buf, int off, int len, int toBit, int m, int[] ks) { int num = (int)((uint)toBit >> 6); while (--len > num) { long num2 = buf[off + len]; if (num2 != 0) { buf[off + len] = 0; ReduceWord(buf, off, len << 6, num2, m, ks); } } int num3 = toBit & 63; long num4 = (long)((ulong)buf[off + num] >> num3); if (num4 != 0) { buf[off + num] ^= num4 << num3; ReduceWord(buf, off, toBit, num4, m, ks); } } private static void ReduceWord(long[] buf, int off, int bit, long word, int m, int[] ks) { int num = bit - m; int num2 = ks.Length; while (--num2 >= 0) { FlipWord(buf, off, num + ks[num2], word); } FlipWord(buf, off, num, word); } private static void ReduceVectorWise(long[] buf, int off, int len, int words, int m, int[] ks) { int num = (words << 6) - m; int num2 = ks.Length; while (--num2 >= 0) { FlipVector(buf, off, buf, off + words, len - words, num + ks[num2]); } FlipVector(buf, off, buf, off + words, len - words, num); } private static void FlipVector(long[] x, int xOff, long[] y, int yOff, int yLen, int bits) { xOff += (int)((uint)bits >> 6); bits &= 63; if (bits == 0) Add(x, xOff, y, yOff, yLen); else { long num = AddShiftedDown(x, xOff + 1, y, yOff, yLen, 64 - bits); x[xOff] ^= num; } } public LongArray ModSquare(int m, int[] ks) { int usedLength = GetUsedLength(); if (usedLength == 0) return this; int num = usedLength << 1; long[] array = new long[num]; int num2 = 0; while (num2 < num) { long num3 = m_ints[(uint)num2 >> 1]; array[num2++] = Interleave2_32to64((int)num3); array[num2++] = Interleave2_32to64((int)((ulong)num3 >> 32)); } return new LongArray(array, 0, ReduceInPlace(array, 0, array.Length, m, ks)); } public LongArray ModSquareN(int n, int m, int[] ks) { int num = GetUsedLength(); if (num == 0) return this; long[] array = new long[m + 63 >> 6 << 1]; Array.Copy(m_ints, 0, array, 0, num); while (--n >= 0) { SquareInPlace(array, num, m, ks); num = ReduceInPlace(array, 0, array.Length, m, ks); } return new LongArray(array, 0, num); } public LongArray Square(int m, int[] ks) { int usedLength = GetUsedLength(); if (usedLength == 0) return this; int num = usedLength << 1; long[] array = new long[num]; int num2 = 0; while (num2 < num) { long num3 = m_ints[(uint)num2 >> 1]; array[num2++] = Interleave2_32to64((int)num3); array[num2++] = Interleave2_32to64((int)((ulong)num3 >> 32)); } return new LongArray(array, 0, array.Length); } private static void SquareInPlace(long[] x, int xLen, int m, int[] ks) { int num = xLen << 1; while (--xLen >= 0) { long num2 = x[xLen]; x[--num] = Interleave2_32to64((int)((ulong)num2 >> 32)); x[--num] = Interleave2_32to64((int)num2); } } private static void Interleave(long[] x, int xOff, long[] z, int zOff, int count, int width) { switch (width) { case 3: Interleave3(x, xOff, z, zOff, count); break; case 5: Interleave5(x, xOff, z, zOff, count); break; case 7: Interleave7(x, xOff, z, zOff, count); break; default: Interleave2_n(x, xOff, z, zOff, count, BitLengths[width] - 1); break; } } private static void Interleave3(long[] x, int xOff, long[] z, int zOff, int count) { for (int i = 0; i < count; i++) { z[zOff + i] = Interleave3(x[xOff + i]); } } private static long Interleave3(long x) { return (x & -9223372036854775808) | Interleave3_21to63((int)x & 2097151) | (Interleave3_21to63((int)((ulong)x >> 21) & 2097151) << 1) | (Interleave3_21to63((int)((ulong)x >> 42) & 2097151) << 2); } private static long Interleave3_21to63(int x) { int num = INTERLEAVE3_TABLE[x & 127]; int num2 = INTERLEAVE3_TABLE[((uint)x >> 7) & 127]; return ((INTERLEAVE3_TABLE[(uint)x >> 14] & uint.MaxValue) << 42) | ((num2 & uint.MaxValue) << 21) | (num & uint.MaxValue); } private static void Interleave5(long[] x, int xOff, long[] z, int zOff, int count) { for (int i = 0; i < count; i++) { z[zOff + i] = Interleave5(x[xOff + i]); } } private static long Interleave5(long x) { return Interleave3_13to65((int)x & 8191) | (Interleave3_13to65((int)((ulong)x >> 13) & 8191) << 1) | (Interleave3_13to65((int)((ulong)x >> 26) & 8191) << 2) | (Interleave3_13to65((int)((ulong)x >> 39) & 8191) << 3) | (Interleave3_13to65((int)((ulong)x >> 52) & 8191) << 4); } private static long Interleave3_13to65(int x) { int num = INTERLEAVE5_TABLE[x & 127]; return ((INTERLEAVE5_TABLE[(uint)x >> 7] & uint.MaxValue) << 35) | (num & uint.MaxValue); } private static void Interleave7(long[] x, int xOff, long[] z, int zOff, int count) { for (int i = 0; i < count; i++) { z[zOff + i] = Interleave7(x[xOff + i]); } } private static long Interleave7(long x) { return (x & -9223372036854775808) | INTERLEAVE7_TABLE[(int)x & 511] | (INTERLEAVE7_TABLE[(int)((ulong)x >> 9) & 511] << 1) | (INTERLEAVE7_TABLE[(int)((ulong)x >> 18) & 511] << 2) | (INTERLEAVE7_TABLE[(int)((ulong)x >> 27) & 511] << 3) | (INTERLEAVE7_TABLE[(int)((ulong)x >> 36) & 511] << 4) | (INTERLEAVE7_TABLE[(int)((ulong)x >> 45) & 511] << 5) | (INTERLEAVE7_TABLE[(int)((ulong)x >> 54) & 511] << 6); } private static void Interleave2_n(long[] x, int xOff, long[] z, int zOff, int count, int rounds) { for (int i = 0; i < count; i++) { z[zOff + i] = Interleave2_n(x[xOff + i], rounds); } } private static long Interleave2_n(long x, int rounds) { while (rounds > 1) { rounds -= 2; x = (Interleave4_16to64((int)x & 65535) | (Interleave4_16to64((int)((ulong)x >> 16) & 65535) << 1) | (Interleave4_16to64((int)((ulong)x >> 32) & 65535) << 2) | (Interleave4_16to64((int)((ulong)x >> 48) & 65535) << 3)); } if (rounds > 0) x = (Interleave2_32to64((int)x) | (Interleave2_32to64((int)((ulong)x >> 32)) << 1)); return x; } private static long Interleave4_16to64(int x) { int num = INTERLEAVE4_TABLE[x & 255]; return ((INTERLEAVE4_TABLE[(uint)x >> 8] & uint.MaxValue) << 32) | (num & uint.MaxValue); } private static long Interleave2_32to64(int x) { int num = INTERLEAVE2_TABLE[x & 255] | (INTERLEAVE2_TABLE[((uint)x >> 8) & 255] << 16); return (((INTERLEAVE2_TABLE[((uint)x >> 16) & 255] | (INTERLEAVE2_TABLE[(uint)x >> 24] << 16)) & uint.MaxValue) << 32) | (num & uint.MaxValue); } public LongArray ModInverse(int m, int[] ks) { int num = Degree(); switch (num) { case 0: throw new InvalidOperationException(); case 1: return this; default: { LongArray longArray = Copy(); int intLen = m + 63 >> 6; LongArray longArray2 = new LongArray(intLen); ReduceBit(longArray2.m_ints, 0, m, m, ks); LongArray longArray3 = new LongArray(intLen); longArray3.m_ints[0] = 1; LongArray longArray4 = new LongArray(intLen); int[] array = new int[2] { num, m + 1 }; LongArray[] array2 = new LongArray[2] { longArray, longArray2 }; int[] array3 = new int[2] { 1, 0 }; LongArray[] array4 = new LongArray[2] { longArray3, longArray4 }; int num2 = 1; int num3 = array[num2]; int num4 = array3[num2]; int num5 = num3 - array[1 - num2]; while (true) { if (num5 < 0) { num5 = -num5; array[num2] = num3; array3[num2] = num4; num2 = 1 - num2; num3 = array[num2]; num4 = array3[num2]; } array2[num2].AddShiftedByBitsSafe(array2[1 - num2], array[1 - num2], num5); int num6 = array2[num2].DegreeFrom(num3); if (num6 == 0) break; int num7 = array3[1 - num2]; array4[num2].AddShiftedByBitsSafe(array4[1 - num2], num7, num5); num7 += num5; if (num7 > num4) num4 = num7; else if (num7 == num4) { num4 = array4[num2].DegreeFrom(num4); } num5 += num6 - num3; num3 = num6; } return array4[1 - num2]; } } } public override bool Equals(object obj) { return Equals(obj as LongArray); } public virtual bool Equals(LongArray other) { if (this == other) return true; if (other == null) return false; int usedLength = GetUsedLength(); if (other.GetUsedLength() != usedLength) return false; for (int i = 0; i < usedLength; i++) { if (m_ints[i] != other.m_ints[i]) return false; } return true; } public override int GetHashCode() { int usedLength = GetUsedLength(); int num = 1; for (int i = 0; i < usedLength; i++) { long num2 = m_ints[i]; num *= 31; num ^= (int)num2; num *= 31; num ^= (int)((ulong)num2 >> 32); } return num; } public LongArray Copy() { return new LongArray(Arrays.Clone(m_ints)); } public override string ToString() { int usedLength = GetUsedLength(); if (usedLength == 0) return "0"; StringBuilder stringBuilder = new StringBuilder(Convert.ToString(m_ints[--usedLength], 2)); while (--usedLength >= 0) { string text = Convert.ToString(m_ints[usedLength], 2); int length = text.Length; if (length < 64) stringBuilder.Append("0000000000000000000000000000000000000000000000000000000000000000".Substring(length)); stringBuilder.Append(text); } return stringBuilder.ToString(); } } }